数据结构与算法之图的存储(邻接矩阵法)

• 说明
• 邻接矩阵法
• • 邻接矩阵法存储不带权图
  • • 代码示例
    • 思考
  • 邻接矩阵法存储带权图 (网)
  • • 代码示例
  • 邻接矩阵法的性质
• 邻接矩阵要点回顾：

图有以下四种存储方式

1. 邻接矩阵
2. 邻接表
3. 十字链表
4. 邻接多重表

表示方法如下图：

1. 无向图

#define MaxVertxtNum 100  //项目数目的最大值
typedef char Vertextype; //顶点的数据类型
typedef int Edge;
struct{
	char Vex[MaxVertxtNum];  //顶点表
	int Edge[MaxVertxtNum][MaxVertxtNum];  //邻接矩阵，边表，改成bool或者枚举类型，可以减低内存的使用
	int vexnum,arrnum;  //图的当前顶点和边数/弧数
}MGraph;

结点数为 n 的图 G=(V,E) 的邻接矩阵 A 是 n ∗ n n*n n∗n的。将 G 的顶点编号为 v 1 v_1 v1​, v 2 v_2 v2​,…, v n v_n vn​，则 A [ i ] [ j ] A[i][j] A[i][j]：

1. 1，若 ( v i , v j ) (v_i,v_j) (vi​,vj​)或 < v i > 是 E ( G ) E(G) E(G)中的边
2. 0，若 ( v i , v j ) (v_i,v_j) (vi​,vj​)或 < v i > 不是 E ( G ) E(G) E(G)中的边

如何求顶点的度，入度，出度？

1. 度：第 i 个结点的度：第 i 行 (或第 i 列)==的非零元素个数
2. 出度：第 i 个结点的出度=第 i 行的非零元素个数
3. 入度：第 i 个结点的入度=第 i 列的非零元素个数
   邻接矩阵法求顶点的度/出度/入度的时间复杂度为 O ( ∣ V ∣ ) O(|V|) O(∣V∣)

结构如下图：

#define MaxVertextNum 100  //顶点数目的最大值
#define INFINTY //最大的int值，宏定义变量“无穷”
typedef char Vertextype; //顶点的数据类型
typedef int EdgeType;  //带权图中边上权值的数据类型
typedef struct{
	Vertxtype Vex[MaxVertextNum]; //顶点
	EdgeType Edge[MaxVertextNum][MaxVertextNum]; //边的权
	int vexnum,arcnum;  //图的当前顶点数和弧数
}MGraph;

1. 空间复杂度： O ( ∣ V ∣ 2 ) O({|V|}^2) O(∣V∣2)——只和顶点数相关，和实际的边数无关
2. 适合用于存储稠密图
3. 无向图的邻接矩阵是对称矩阵，可以压缩存储 (只存储上三角区/下三角区)

设图 G 的邻接矩阵为 A(矩阵元素为 0/1)，则 A n A^n An的元素 A n [ i ] [ j ] A^n[i][j] An[i][j]等于顶点 i 到顶点 j 的长度为 n 的路径的数目

结合上图说明：
以 a 1 , 2 a_{1,2} a1,2​， a 2 , 4 a_{2,4} a2,4​为例， a 1 , 2 a_{1,2} a1,2​为 A->B 距离为：1， a 2 , 4 a_{2,4} a2,4​为 B->D 的距离为：1，相乘则表示：A->B->D.

1. 如何计算指定顶点的度、入度、出度（分无向图、有向图来考虑）？时间复杂度如何？
2. 如何找到与顶点相邻的边（入边、出边）？时间复杂度如何？
3. 如何存储带权图？
4. 空间复杂度——O(|V|2)，适合存储稠密图
5. 无向图的邻接矩阵为对称矩阵，如何压缩存储？
6. 设图 G 的邻接矩阵为 A（矩阵元素为 0/1），则 An 的元素 An[i][j] 等于由顶点 i 到顶点 j 的长度为 n 的路径的数目