邻接矩阵

图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图。⼀
个⼀维数组存储图中顶点信息，⼀个⼆维数组（称为邻接矩阵）存储图中
的边或弧的信息。
假设存储下面的一个无向图

定义如下的数据结构

//图的邻接矩阵存储结构
typedef struct  Graph{
	//顶点表
	vector<string> Vexs;
	//边表，表示顶点与顶点之间的连接关系
	vector<vector<int>> arc;
	//存储顶点和边的个数
	int Vertexs,Edges;
}Graph;

注：此处参考《大话数据结构》，书中的Vexs和arc的数据结构感觉使用起来不方便，因此改为C++中支持的string ，vector。

创建图

定义完了图的基础数据结构以后则开始创造一个图。

void CreateGraph(Graph *G)
{
	cout << "请输入顶点个数和边的个数" <<endl;
	cin >> G->Vertexs >> G->Edges;
	cout << "请输入顶点信息" << endl;
	for (int i = 0; i < G->Vertexs; ++i)
	{
		string tmp;
		cin >> tmp;
		G->Vexs.push_back(tmp);
	}
	//边表初始化
	vector<vector<int>> data(G->Vertexs, vector<int>(G->Vertexs, 0));
	G->arc = data;
	for (int i = 0; i < G->Vertexs; ++i){
		for (int j = 0; j < G->Vertexs; ++j){
			//因为是对称矩阵
			if (i != j)
			{
				G->arc[i][j] = 1000;
				G->arc[j][i] = 1000;
			}
		}
	}
	//边表正式录入数据
	for (int k = 0; k < G->Edges; ++k){
		int i,j;
		cout << "请输入边（Vi,Vj）" << endl;
		cin >> i >> j;
		//（Vi,Vj）是连通的顶点，则acr[i][j]与arc[j][i]都为1 
		G->arc[i][j] = 1;
		G->arc[j][i] = 1;
	}
	return;
}

此处使用vector 创建二维矩阵的优势就体现出来了，不用给一个设定的MAX值，有时候用不完，浪费空间，有时候又不够用，很麻烦！且顶点的信息现在就可以实现多样化的输入了，比如：V0、V1或者是A、B等等。

emmm ,还写了一个打印图的函数。

//打印连接链表
void PrintGraph(Graph *G)
{
	cout << "所建立的矩阵表如以下所示：" << endl;
	for (int i = 0; i<G->Vertexs; i++)
	{
		cout << G->Vexs[i]<<"：";             //先输出顶点信息
		for (int j = 0; j<G->Vertexs; ++j) //然后就开始遍历输出每个边表所存储的邻接点的下标
		{
			cout << G->arc[i][j] ;
		}
		cout << endl;
	}
}

创建一个全局的访问数组

bool Visted[100];

深度优先遍历（DFS）

下面开始以邻接矩阵实现图数据结构的深度优先遍历。

//DFS
void DFS(Graph *G, int i)
{
	//只要你进来了，就说明你已经访问了
	Visted[i] = true;
	cout << "当前节点为：" << G->Vexs[i];
	for (int j = 0; j < G->Vertexs; ++j){
		//arc[i][j]之间要有通路，并且J还没有被访问
		if (G->arc[i][j] == 1 && !Visted[j])
			DFS(G, j);
	}
	cout << endl;
}
void DFSTraver(Graph *G)
{
	//将访问列表初始化
	cout << "DFS遍历顺序为" << endl;
	for (int i = 0; i < G->Vertexs; ++i){
		Visted[i] = false;
	}
	for (int i = 0; i < G->Vertexs; ++i){
		if (!Visted[i])
			DFS(G, i);
	}
}

其实就是一个递归，很像二叉树的三种普通遍历方法。

广度优先遍历(BFS)

广度优先遍历很像是二叉树的层序遍历，此处需要用到栈（stack）这个辅助的数据结构，因此使用C++也就会方便很多。

//BFS  特点要使用队列，很像树的层序遍历
void BFSTraver(Graph *G)
{
	cout << "BFS遍历顺序为" << endl;
	//辅助队列
	queue<int> Q;
	//同样要初始化访问数组
	for (int i = 0; i < G->Vertexs; ++i)
		Visted[i] = false;
	//开始对每个顶点循环
	for (int i = 0; i < G->Vertexs; ++i){
		if (!Visted[i]){
			Q.push(i);
			Visted[i] = true;
			cout << "当前节点为：" << G->Vexs[i];
			while(!Q.empty()){
				i = Q.front();
				Q.pop();
				for (int j = 0; j < G->Vertexs; ++j){
					if (G->arc[i][j] == 1 && !Visted[j]){
						Visted[j] = true;
						cout << "当前节点为：" << G->Vexs[j];
						Q.push(j);

					}
				}
			}
		}
	}
	return;
}

测试一下

emmm ,写完以后就开始测试了。测试的图信息如下所示。

结果。

emmm ,因为顶点之间没有连接的时候用1000表示，（V0，V0）在矩阵中用0表示，（V0，V1）用1表示，所以二维矩阵看着有些乱。
图的邻接矩阵就酱紫吧！！！