数据结构——图(邻接矩阵)

2019/7/21 14:18:02 人评论 次浏览 分类:学习教程

邻接矩阵

图的邻接矩阵(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表示,所以二维矩阵看着有些乱。
图的邻接矩阵就酱紫吧!!!

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->