有向图的邻接矩阵

有向图的邻接矩阵是一种表示有向图的方法，其中矩阵的每个元素表示两个顶点之间是否有边以及边的权重。具体规则如下：

  1. 矩阵大小 ：邻接矩阵是一个 \( n \times n \) 的二维数组，其中 \( n \) 是图中顶点的数量。

  2. 元素值 ：

  • 如果从顶点 \( vi \) 到顶点 \( vj \) 有一条边，则邻接矩阵 \( M[i][j] = 1 \)。

  • 如果两个顶点之间没有边，则邻接矩阵 \( M[i][j] = 0 \)。

  • 如果需要表示图中边的权重，则可以将 \( 1 \) 替换为边的权重值，将 \( 0 \) 替换为无穷大(∞)表示没有直接的边。

  1. 对称性 ：无向图的邻接矩阵是对称的，即 \( M[i][j] = M[j][i] \)。但有向图的邻接矩阵不一定对称，因为边的方向不同。

  2. 行和列的解读 ：

  • 第 \( i \) 行表示以顶点 \( vi \) 为终点的所有边及其权重。

  • 第 \( i \) 列表示以顶点 \( vi \) 为起点的所有边及其权重。

  1. 特殊值 ：
  • 对角线上的元素 \( M[i][i] \) 通常表示顶点 \( vi \) 到自身的距离，在没有自环的情况下，这个值应该是 \( 0 \) 或未定义。

示例

假设有向图如下：

V1 -> V2 (权重18)
V1 -> V3 (权重3)
V2 -> V3 (权重5)
V2 -> V5 (权重4)
V4 -> V2 (权重15)
V5 -> V4 (权重12)

其邻接矩阵可以表示为：

18  3  0  0  0  0
 0  1  5  4  0  0
 0  0  1  0  0  0
 0  15  0  1  0  0
 0  0  0  0  1  0
 0  0  0  0  0  1

在这个矩阵中：

  • \( M = 18 \) 表示从 V1 到 V2 有一条权重为 18 的边。

  • \( M = 5 \) 表示从 V2 到 V1 有一条权重为 5 的边。

  • 其他 \( M[i][j] = 0 \) 表示没有直接的边。

注意

  • 邻接矩阵的空间复杂度是 \( O(n^2) \)，其中 \( n \) 是顶点的数量。

  • 对于稠密图(边数接近 \( n^2 \))，邻接矩阵是高效的表示方法。但对于稀疏图(边数远小于 \( n^2 \))，使用邻接表会更节省空间。

Top
×
×