图存储之邻接矩阵法

客官°小女子只卖身不卖艺 2022-12-15 12:59 149阅读 0赞

## 一 概述 ##

图的存储必须要完整，准确地反映顶点集和边集的信息。根据不同图的结构和算法，采用不同的存储方式将对程序的效率产生相当大的影响。

## 二 邻接矩阵法 ##

邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息，即各顶点之间的邻接关系，存储顶点之间邻接关系的二维数组称为邻接矩阵。

结点数为n的图G=\{V，E\}的邻接矩阵A是n×n的n阶矩阵，将G的顶点编号为v1，v2，...，vn。若(vi，vj)∈E，则A\[i\]\[j\]=1，否者使得A\[i\]\[j\]=0。

![20201017092520260.png][]

对于带权图而言，若顶点vi和vj之间有边相连，则邻接矩阵中对应项存放着该边对应的权值，若顶点vi和vj不相连，则用**∞**代表这两个顶点之间不存在的边。

![20201017092757403.png][]

<table> 
 <tbody> 
  <tr> 
   <td>有向图及其邻接矩阵</td> 
   <td><img alt="" height="77" src="https://img-blog.csdnimg.cn/20201017092914933.png" width="173"></td> 
   <td>无向图及其邻接矩阵</td> 
   <td><img alt="" height="81" src="https://img-blog.csdnimg.cn/20201017092926719.png" width="190"></td> 
   <td>网及其邻接矩阵</td> 
   <td><img alt="" height="92" src="https://img-blog.csdnimg.cn/20201017092952219.png" width="284"></td> 
  </tr> 
 </tbody> 
</table>

## 三 邻接矩阵的存储结构 ##

#define MaxVertexNum 100        //顶点数目的最大值
    typedef char VertexType;        //顶点数据类型
    typedef int EdgeType;           //带权图中边上权值的数据类型
    typedef struct {
        VertexType Vex[MaxVertexNum]; //顶点表
        EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵，边表
        int vexnum,arcnum; //图的当前顶点数和弧数
    }Mgraph;

注意：

1.  在简单应用中，可直接用二维数组作为图的邻接矩阵（顶点信息等均可省略）。
2.  当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeType可定义为值为0和1的枚举类型。
3.  无向图的邻接矩阵是对称矩阵，对规模大的邻接矩阵可采用压缩存储。
4.  邻接矩阵表示法的空间复杂度为O(n^2)，其中n为图的顶点数|V|。

## 四 图的邻接矩阵存储表示法的特点 ##

1.  无向图的邻接矩阵一定是一个对称矩阵(并且唯一)。因此，在实际存储邻接矩阵时只需要存储上（或下）三角矩阵的元素。
2.  对于无向图，邻接矩阵的第i行(或第i列)非零元素(或非∞元素)的个数正好是第i个顶点的度，如上无向图及其邻接矩阵看顶点3对应的非零元素为3个，所以顶点3的度为3。
3.  对于有向图，邻接矩阵的第i行(或低i列)非零元素(或非∞元素)的个数正好是第i个顶点的出度或者入度，如上有向图及其邻接矩阵，顶点1对应的非零元素为2个，所以顶点1的出度为2。
4.  用邻接矩阵法存储图，很容易确定图中任意两个顶点之间是否有变相连。但是，要确定图中有多少条边，则必须按行，按列对每个元素进行检测，所花费的时间代价很大。
5.  稠密图适合使用邻接矩阵的存储表示。
6.  设图G的邻接矩阵为A，A^n的元素A^n\[i\]\[j\]等于由顶点i到顶点j的长度为n的路径的数目。

[20201017092520260.png]: /images/20221123/874629b9ae1549d3af40fadfb10a9698.png
[20201017092757403.png]: /images/20221123/fa71842984e645749fcb23d2142e7377.png