数据结构——图——存储结构——邻边矩阵

一时失言乱红尘 2023-01-10 03:42 22阅读 0赞

## 数据结构——图——存储结构——邻边矩阵 ##

考虑到图是由顶点和边或弧两部分组成。合在一起比较困难，那就很自然地考虑到分两个结构来分别存储。顶点不分大小、主次，所以用一个一维数组来存储是很不错的选择。而边或弧由于是顶点与顶点之间的关系，一维搞不定，那就考虑用一个二维数组来存储。于是我们的邻接矩阵的方案就诞生了。

图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

设图G有n个顶点，则邻接矩阵是一个n×n的方阵，定义为:  
![在这里插入图片描述][20210122174018791.png]

我们来看一个实例，图7-4-2的左图就是一个无向图。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70]  
我们可以设置两个数组，顶点数组为vertex\[4\]=\{ vo, v1, v2, v3\}，边数组arc\[4\]\[4\]为图7-4-2右图这样的一个矩阵。简单解释一下，对于矩阵的主对角线的值，即arc\[0\]\[0\]、arc\[1\]\[1\]、arc\[2\]\[2\]、arc\[3\]\[3\]，全为О是因为不存在顶点到自身的边，比如v到vo。arc\[0\]\[1\]=1是因为vo到vi的边存在，而arc\[1\]\[3\]=0是因为vi到v3的边不存在。并且由于是无向图，v1到v3的边不存在，意味着v3到v的边也不存在。所以无向图的边数组是一个对称矩阵。

嗯?对称矩阵是什么?忘记了不要紧，复习一下。所谓对称矩阵就是n 阶矩阵的元满足aj=aj，(0≤ij≤n)。即从矩阵的左上角到右下角的主对角线为轴，右上角的元与左下角相对应的元全都是相等的。

有了这个矩阵,我们就可以很容易地知道图中的信息。  
1．我们要判定任意两顶点是否有边无边就非常容易了。  
2．我们要知道某个顶点的度，其实就是这个顶点v在邻接矩阵中第i行(或第i列)的元素之和。比如顶点v的度就是1+0+1+0=2。  
3．求顶点v的所有邻接点就是将矩阵中第i行元素扫描一遍，arc\[i\]i\]为1就是邻接点。

我们再来看一个有向图样例，如图7-4-3所示的左图。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 1]  
顶点数组为vertex\[4\]=\{ vo,v1, V2, V3\}，弧数组arc\[4\]\[4\]为图7-4-3右图这样的一个矩阵。主对角线上数值依然为0。但因为是有向图，所以此矩阵并不对称，比如由v1到vo有弧,得到arc\[1\]\[0\]=1，而v到v没有弧，因此arc\[0\]\[1\]=0。

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

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

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

设图G是网图，有n个顶点，则邻接矩阵是一个n×n的方阵，定义为:  
![在这里插入图片描述][20210122174708746.png]  
这里 wij表示(v,)）或上的权值。oo表示一个计算机允许的、大于所有边上权值的值，也就是一个不可能的极限值。有同学会问，为什么不是0呢?原因在于权值wj大多数情况下是正值，但个别时候可能就是0，甚至有可能是负值。因此必须要用一个不可能的值来代表不存在。如图7-4-4左图就是一个有向网图，右图就是它的邻接矩阵。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 2]  
那么邻接矩阵是如何实现图的创建的呢?我们先来看看图的邻接矩阵存储的结构，代码如下。

typedef char VertexType;  /*顶点类型应由用户定义*/
    
    typedef int EdgeType; /*边上的权值类型应由用户定义*/
    
    #define MAXVEX 100   /*最大顶点数，应由用户定义*/
    
    #define INFINITY 65535  /*用65535来代表*/
    
    typedef struct
    {
        
    	VertexType vexs[MAXVEX];   /*顶点表*/
    	EdgeType arc[MAXVEX][MAXVEX];  /*领边矩阵，可看作边表*/
    
    	int numVertexes, numEdges;    /*图中当前的顶点树和边树*/
    } MGraph;

有了这个结构定义，我们构造一个图，其实就是给顶点表和边表输入数据的过程。我们来看看无向网图的创建代码。

/*建立无向网图的邻接矩阵表示*/
    void CreateMGraph(MGraph* G)
    {
        
    	int i, j, k, w;
    	printf("输入顶点数和边数：\n");
    	scanf("%d,%d", &G->numVertexes, &G->numEdges);/*输入顶点数和边数*/
    	for (i=0;i<G->numVertexes;i++)/*读入顶点信息，建立顶点表*/
    	{
        
    		scanf(&G->vexs[i]);
    	}
    	for (i = 0; i < G->numVertexes; i++)
    	{
        
    		for (j = 0; j < G->numVertexes; 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[i][j] = G->arc[i][j];/*因为是无向图，矩阵对称*/
    	}
    }

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

[20210122174018791.png]: /images/20221119/592b88d4753145349074612326168db7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70]: /images/20221119/4c210b6b7c6f4611be708777cdd606f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 1]: /images/20221119/c562f13148a54ed6978754b4ce70ca5e.png
[20210122174708746.png]: /images/20221119/856e6ac1b06449198551cd524b25dd84.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 2]: /images/20221119/17153c4431494b2bb619c7b648a40951.png