什么是邻接矩阵？

在本文中，我们将讨论邻接矩阵及其表示方法。

邻接矩阵定义

在图论中，邻接矩阵是一种描述有限图结构的密集表示方法。它是一个二维矩阵，用于映射图节点之间的关联。

如果一个图有 n 个顶点，则该图的邻接矩阵为 n x n，矩阵的每个条目表示从一个顶点到另一个顶点的边的数量。

邻接矩阵也称为连接矩阵。有时也称为顶点矩阵。

邻接矩阵表示

如果一个无向图 G 包含 n 个顶点，则图的邻接矩阵是一个 n x n 矩阵 A = [aij]，其定义如下：

a_ij = 1 {如果存在从 V_i 到 V_j 的路径}

a_ij = 0 {否则}

让我们来看一些关于邻接矩阵的重要要点。

• 如果顶点 V_i 和 V_j 之间存在一条边，其中 i 是行，j 是列，则 a_ij = 1。
• 如果顶点 V_i 和 V_j 之间没有边，则 a_ij = 0。
• 如果简单图中没有自环，则顶点矩阵（或邻接矩阵）的对角线应为 0。
• 无向图的邻接矩阵是对称的。这意味着第 i 行第 j 列的值等于第 j 行第 i 列的值。
• 如果邻接矩阵自身相乘，并且第 i 行第 j 列存在非零值，则表示存在一条长度为 2 的从 V_i 到 V_j 的路径。邻接矩阵中的非零值表示存在不同路径的数量。

注意：在邻接矩阵中，0 表示两个节点之间不存在关联，而 1 表示两个节点之间存在关联。

如何创建邻接矩阵？

假设有一个包含 n 个顶点的图 g，则顶点矩阵（或邻接矩阵）为：

A =    a11 a12 . . . . . a1n
       a21 a22 . . . . . a2n
       .     .          .
       .     .          .
       .     .          .
       an1 an2 . . . . . ann

其中 a_ij 等于从顶点 i 到顶点 j 的边的数量。如上所述，无向图的邻接矩阵是对称的，因此对于无向图，a_ij = a_ji。

当图是简单图且边上没有权重或多重边时，邻接矩阵的条目将是 0 和 1。如果没有自环，则邻接矩阵的对角线条目将为 0。

现在，让我们来看一下无向图和有向图的邻接矩阵。

无向图的邻接矩阵

在无向图中，边不关联方向。在无向图中，如果顶点 A 和顶点 B 之间存在一条边，则可以从 A 到 B 以及从 B 到 A 进行传输。

让我们来看下面的无向图，并尝试构建它的邻接矩阵。

在图中，我们可以看到没有自环，因此邻接矩阵的对角线条目将为 0。上述图的邻接矩阵将是：

有向图的邻接矩阵

在有向图中，边形成一个有序对。边表示从某个顶点 A 到另一个顶点 B 的特定路径。顶点 A 称为起始节点，而顶点 B 称为终止节点。

让我们来看下面的有向图，并尝试构建它的邻接矩阵。

在上面的图中，我们可以看到没有自环，因此邻接矩阵的对角线条目将为 0。上述图的邻接矩阵将是：

邻接矩阵的性质

邻接矩阵的一些性质列出如下：

• 邻接矩阵是一个包含行和列的矩阵，用于表示具有 0 和 1 的简单标记图，在 (V_I, V_j) 的位置，根据两个 V_i 和 V_j 是否相邻的条件。
• 对于有向图，如果存在从顶点 i 或 V_i 到顶点 j 或 V_j 的边，则 A[V_i][V_j] = 1，否则值为 0。
• 对于无向图，如果存在从顶点 i 或 V_i 到顶点 j 或 V_j 的边，则 A[V_i][V_j] = 1 且 A[V_j][V_i] = 1，否则值为 0。

让我们来看一些关于邻接矩阵的问题。以下问题涉及加权无向图和加权有向图。

注意：如果每条边都分配了一个正数，称为边的权重，则称该图为加权图。

问题 1 - 下面无向加权图的邻接矩阵是什么？

解答 - 在给定的问题中，没有自环，因此可以清楚地知道上述图的邻接矩阵的对角线条目为 0。上述图是加权无向图。图边上的权重将表示为邻接矩阵的条目。

上述图的邻接矩阵将是：

问题 2 - 下面有向加权图的邻接矩阵是什么？

解答 - 在给定的问题中，没有自环，因此可以清楚地知道上述图的邻接矩阵的对角线条目为 0。上述图是加权有向图。图边上的权重将表示为邻接矩阵的条目。

上述图的邻接矩阵将是：

希望本文对您理解邻接矩阵有所帮助。在这里，我们讨论了邻接矩阵的创建和性质。我们还讨论了在有向或无向图（无论是否加权）上形成邻接矩阵。