数据结构_图—邻接矩阵(C语言)

(一) 邻接矩阵图文解析

<mark>建议先学完《线性代数》，那样邻接矩阵就非常容易理解了</mark>
邻接矩阵主要是对矩阵的理解，首先要理解矩阵是什么，简单的说矩阵就是二维数组，我们可以根据行列位置来描述行与列的关系；
如果2行3列的值是5，那么我也可以这么理解，2+3=5，这样就很清楚的表示了两者之间的关系
如果2行3列的值是无穷大∞，2不等于3，那么我们就可以理解他们不相等，或者没关系

然后我们要知道什么是图，就像地图一样，一个城市连着许多城市，城市之间彼此相互连接

最后结合二者就是图的邻接矩阵：
1. 先用一个一维数组数组单独存储每个顶点的信息，比如可以代表城市名、地名等，
2. 再用二维数组代表俩个顶点的联系，成为俩顶点的边，边上值叫做权值，代表着俩顶点之间的信息，比如可以代表距离，行车时间等；
3. 该图是无向图，意思是两个城市之间可以相互往来，所以矩阵是对称的。

(二) 邻接矩阵代码解析

2.1 邻接矩阵的存储结构

typedef struct
{
	VertexType vexs[MAXVEX];//一维数组，用于存储顶点信息
	EdgeType arc[MAXVEX][MAXVEX];// 二维数组，用于存储边的权值
	int numNodes,numEdges;//邻接矩阵的顶点数和边数
}MGraph;

2.2 邻接矩阵的创建

void CreateMGraph(MGraph &G)
{
	int i,j,k,w;
	printf("请输入顶点数和边数:");
	scanf("%d %d",&G.numNodes,&G.numEdges);
	fflush(stdin);	
	for(i=0;i<G.numNodes;i++)
	{
		printf("请第%d个顶点信息:",i+1);
		scanf("%c",&G.vexs[i]);
		fflush(stdin);	
	}
	for(i=0;i<G.numNodes;i++)
		for(j=0;j<G.numNodes;j++)
			G.arc[i][j]=INF;//初始化二维数组的值都为INF

	for(k=0;k<G.numEdges;k++)
	{
		printf("请输入第%d条边的两个顶点及其权值:",k+1);
		scanf("%d %d %d",&i,&j,&w);
		G.arc[i-1][j-1]=w;//将权值赋给该二维数组中对应的边
		G.arc[j-1][i-1]=w;//无向图，权值在二位数组中对称
		//如果是有向图无需最后一段代码，即俩顶点之间可能不互通，一条边只有一个方向
	}
}

2.3 邻接矩阵的遍历

void TravelMGraph(MGraph G)
{
	int i,j;
	for(i=0;i<G.numNodes;i++)
	{
		for(j=0;j<G.numNodes;j++)
		{	
			if(G.arc[i][j]==INF)
				printf("∞\t");//用∞代表俩顶点之间无联系
				else
					printf("%d\t",G.arc[i][j]);
		}
		printf("\n");
	}
}

2.4 邻接矩阵的查找

void LocateMGraph(MGraph G)
{
	int i,j;
	printf("请输入需要查找的顶点编号:");
	scanf("%d",&i);
	printf("该顶点信息为:%c\n",G.vexs[i-1]);

	printf("请输入需要查找边的两个顶点编号:");
	scanf("%d %d",&i,&j);
	printf("该边的权值为:%d\n",G.arc[i-1][j-1]);
}

(三)源代码及测试

3.1 源代码

#include<stdio.h>

#define MAXVEX 100
#define INF 65535

typedef char VertexType;
typedef int EdgeType;

typedef struct
{
	VertexType vexs[MAXVEX];
	EdgeType arc[MAXVEX][MAXVEX];
	int numNodes,numEdges;
}MGraph;

void CreateMGraph(MGraph &G)
{
	int i,j,k,w;
	printf("请输入顶点数和边数:");
	scanf("%d %d",&G.numNodes,&G.numEdges);
	fflush(stdin);	
	for(i=0;i<G.numNodes;i++)
	{
		printf("请第%d个顶点信息:",i+1);
		scanf("%c",&G.vexs[i]);
		fflush(stdin);	
	}
	for(i=0;i<G.numNodes;i++)
		for(j=0;j<G.numNodes;j++)
			G.arc[i][j]=INF;		

	for(k=0;k<G.numEdges;k++)
	{
		printf("请输入第%d条边的两个顶点及其权值:",k+1);
		scanf("%d %d %d",&i,&j,&w);
		G.arc[i-1][j-1]=w;
		G.arc[j-1][i-1]=w;
	}
}
void TravelMGraph(MGraph G)
{
	int i,j;
	for(i=0;i<G.numNodes;i++)
	{
		for(j=0;j<G.numNodes;j++)
		{	
			if(G.arc[i][j]==INF)
				printf("∞\t");
				else
					printf("%d\t",G.arc[i][j]);
		}
		printf("\n");
	}

}
void LocateMGraph(MGraph G)
{
	int i,j;
	printf("请输入需要查找的顶点编号:");
	scanf("%d",&i);
	printf("该顶点信息为:%c\n",G.vexs[i-1]);

	printf("请输入需要查找边的两个顶点编号:");
	scanf("%d %d",&i,&j);
	printf("该边的权值为:%d\n",G.arc[i-1][j-1]);
}
int main()
{
	MGraph G;
	CreateMGraph(G);
	printf("邻接矩阵:\n");
	TravelMGraph(G);
	LocateMGraph(G);
	return 0;
}