数据结构(6.2_1)——领接矩阵法

图的存储——邻接矩阵法

邻接矩阵（Adjacency Matrix）是一种使用二维数组来表示图的方法。在这种表示法中，矩阵的行和列都对应图的顶点。

特点

• 对于无向图，如果顶点i与顶点j之间有边，则矩阵的第i行第j列（记作matrix[i][j]）和第j行第i列的元素值为1（或者边的权重），否则为0。
• 对于有向图，如果存在一条从顶点i到顶点j的边，则matrix[i][j]为1（或有向边的权重），否则为0。有向图的邻接矩阵一般不是对称的。
• 邻接矩阵适用于稠密图（边数接近顶点数平方的图）。

表示

• 设图G有V个顶点，则邻接矩阵是一个V x V的矩阵。
• 对于无权图，matrix[i][j]可以是0或1。
• 对于带权图，matrix[i][j]可以是权重值，如果没有直接连接的边，则可以是无穷大或者一个特殊标记（比如null或者Infinity）。

 

优点

• 简单直观。
• 判断两个顶点之间是否存在边的时间复杂度为O(1)。
• 适用于快速查找两个顶点之间的边或计算顶点的度（对于无向图）。

缺点

• 如果图比较稀疏，则空间效率低下，因为很多位置都存储了0。
• 添加或删除顶点时，需要重新分配整个矩阵，成本较高。

 

如何求顶点的度、入度、出度 

无向图：

第i个结点的度=第 i 行(或第i列)的非零元素个数

时间复杂度=O(n)

有向图:

第i个结点的出度=第 i 行的非零元素个数

第i个结点的入度=第 i 列的非零元素个数

第i个结点的度=第 i 行、第i列的非零元素个数之和

邻接矩阵法存储带权图(网) 

带权图（网）是指图中每条边都有一个与之相关的权重。在邻接矩阵法中，带权图的存储可以通过将邻接矩阵中的元素设置为边的权重来表示。以下是带权图（网）使用邻接矩阵存储的详细说明。

特点

• 对于带权图，如果顶点i与顶点j之间有边，则邻接矩阵的第i行第j列（记作matrix[i][j]）的元素值为该边的权重。
• 如果顶点i与顶点j之间没有边，则matrix[i][j]的元素值可以设置为无穷大（或者一个足够大的数，表示两个顶点之间没有直接连接）。
• 对于无向带权图，邻接矩阵是对称的，因为边(i, j)和边(j, i)的权重是相同的。
• 对于有向带权图，邻接矩阵不一定对称，因为边(i, j)的权重可以与边(j, i)的权重不同。

若出现0或∞则代表不存在边

• 方便地表示了边的权重。
• 快速查找两个顶点之间的边的权重，时间复杂度为O(1)。
• 便于计算最短路径等算法。

缺点

• 对于稀疏图，空间效率不高，因为大多数元素都是无穷大，表示没有边。
• 添加或删除顶点时，需要重新分配整个矩阵。

 邻接矩阵的性能分析

空间复杂度：O(|V|^2)——只和顶点数相关，和实际的边数无关

适合存储稠密图

无向图的领接矩阵是对称矩阵，可以压缩存储(只存储上三角区/下三角区)

 领接矩阵法的性质

 

总结：