【数据结构】图的存储结构之邻接矩阵（C语言）

左手的ㄟ右手 2023-02-23 10:59 12阅读 0赞

**图的邻接矩阵（Adjacency Matrix）存储方式使用过两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。**  
![在这里插入图片描述][20200707101826952.png]我们来看一个实例，图1-1的左图就是一个无向图。  
![在这里插入图片描述][20200707101921312.png_pic_center]

图1-1  
我们设置两个数组，顶点数组为vertex\[4\]=\{v 0,v 1,\}v 2,v 3\} ，边数组arc\[4\]\[4\]，如图1-1的右图这样的一个矩阵。简单的解释一下，对于矩阵的对角线的值，即arc\[0\]\[0\]，arc\[1\]\[1\]，arc\[2\]\[2\]，arc\[3\]\[3\],全为0是因为不存在顶点到自身的边，比如v 0到v 0，arc\[0\]\[1\]=1是因为v 0到v 1的边存在，而arc\[1\]\[3\]=0是因为v 1到v 3的边不存在。并且由于是无向图 ，v 1到v 3的边不存在，意味着v 3到v 1的边也不存在。所以无向图的边数组是一个对称矩阵。

所谓对称矩阵就是n阶矩阵的元满足aij = aji，（0≤i，j≤n）.即从矩阵的左上角到右下角的主对角线为轴，右上角的元与左下角相对应的元全都是相等的。

有了这个矩阵，我们家就可以知道图中的信息了。

1.  我们要判断任意两顶点是否有边无边就非常容易了。
2.  我们要知道某个顶点的度，其实就是这个顶点vi在邻接矩阵中第i行（或第i列）的元素之和。比如顶点v1的度就是1+0+1+0=2。
3.  求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍，arc\[i\]\[j\]为1就是邻接点。

看一个有向图样例，如图1-2所示的左图。  
![在这里插入图片描述][20200707114538873.png_pic_center]

图1-2

顶点数组为vertex\[4\]=\{ \{v0,v1,v2,v3\},弧数组arc\[4\]\[4\]为图1-2所示的右图这样的一个矩阵。对角线上数值依然为0，但因为是有向图， 所以矩阵并不对称，比如由v1到v0有弧，得到arc\[1\]\[0\]=1,而v0到v1没有弧，因此arc\[0\]\[1\]=0。

有向图讲究入度和出度，顶点v1的入度为1，正好是第v1列各数之和。顶点v1的出度为2，即第v1行的各数之和。

与无向图同样的办法，判断顶点vi的入度为1，正好是divi到vj是否存在弧，只需要查找矩阵中arc\[i\]\[j\]是否为1即可。要求vi的所有邻接点就是将矩阵第i行元素扫描一遍，查找arc\[i\]\[j\]为1 的顶点。

在图的概念中，提到了网的概念，也就是每条边上带有权的图叫做网。那么这些权值就需要保存下来，如何处理这个矩阵来适应这个需求呢？我们有办法。

设图G是网图，有n个顶点，则邻接矩阵是一个n \*n的方阵，定义为：  
![在这里插入图片描述][2020070712050339.png_pic_center]这里的Wij 表示（vi,vj）上的权值。∞表示一个计算机允许的，大于边上权值的值，也就是一个不可能的极限值。有人问，为什么不是0呢？原因在于权值Wij大多数情况下是正值，但个别时候可能是0，甚至有可能是负值。因此必须利用一个不可能的值来代表不存在，如图1-3就是一个有向网，右图就是他的邻接矩阵。  
![在这里插入图片描述][20200707120946560.png_pic_center]

图1-3

那么邻接矩阵是如何实现图的创建的呢？图的邻接矩阵存储的结构代码如下：

typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
    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("输入顶点数和边数:\n");
    	scanf("%d,%d",&G->numNodes,&G->numEdges); /* 输入顶点数和边数 */
    	for(i = 0;i <G->numNodes;i++) /* 读入顶点信息,建立顶点表 */
    		scanf(&G->vexs[i]);
    	for(i = 0;i <G->numNodes;i++)
    		for(j = 0;j <G->numNodes;j++)
    			G->arc[i][j]=INFINITY;	/* 邻接矩阵初始化 */
    	for(k = 0;k <G->numEdges;k++) /* 读入numEdges条边，建立邻接矩阵 */
    	{
        
    		printf("输入边(vi,vj)上的下标i，下标j和权w:\n");
    		scanf("%d,%d,%d",&i,&j,&w); /* 输入边(vi,vj)上的权w */
    		G->arc[i][j]=w; 
    		G->arc[j][i]= G->arc[i][j]; /* 因为是无向图，矩阵对称 */
    	}
    }

**从代码中也可以得到，n个顶点和e条边的无向网图的创建，时间复杂度为O(n+n2\+e),其中对邻接矩阵Grac的初始化耗费了O（n2）的时间。**

[20200707101826952.png]: https://img-blog.csdnimg.cn/20200707101826952.png
[20200707101921312.png_pic_center]: https://img-blog.csdnimg.cn/20200707101921312.png#pic_center
[20200707114538873.png_pic_center]: https://img-blog.csdnimg.cn/20200707114538873.png#pic_center
[2020070712050339.png_pic_center]: https://img-blog.csdnimg.cn/2020070712050339.png#pic_center
[20200707120946560.png_pic_center]: https://img-blog.csdnimg.cn/20200707120946560.png#pic_center