邻接矩阵详解

邻接矩阵是图论中用于表示图（Graph）结构的一种重要数据结构，特别适用于表示顶点之间连接关系的图形。在计算机科学和数学领域，它被广泛应用来编码无向图和有向图的信息。

对于一个具有 n 个顶点的图 G=(V,E)，邻接矩阵是一个 n×n 的矩阵 A，其中的行和列分别对应着图中的每个顶点。矩阵中的每个元素 (A[i][j]) 表示从顶点 i 到顶点 j 存在边的情况：

• 在无向图中，如果顶点 i 和顶点 j 之间有一条边相连，则 (A[i][j] = A[j][i] = 1)（或者根据具体实现可能是其他非零值），由于无向图的边是双向的，所以邻接矩阵是对称的。

• 在有向图中，如果从顶点 i 有一条指向顶点 j 的有向边，则 (A[i][j] = 1)，但并不意味着必须有 (A[j][i] = 1)。这意味着有向图的邻接矩阵可能不是对称的。

此外，在某些情况下，邻接矩阵的元素还可以存储边的权重或其他属性信息，例如在带权图中，矩阵的每个非零元素可以是对应边的权重值。

利用邻接矩阵，可以方便地进行图的各种操作和分析，比如判断任意两点间是否存在边、计算节点的度数、查找路径以及进行图的遍历等等。然而，对于稀疏图（即边的数量远小于顶点数量平方的图），邻接矩阵可能会占用较大的存储空间，这时邻接表等其他数据结构可能会更加高效。

在图论中，网（Network）是指带有权重的图，其中边或弧可以具有非零的权值，通常代表距离、成本或其他度量。对于这样的带权图，其邻接矩阵的表示会包含每个顶点对之间的权值信息。

网的邻接矩阵 是一个 n×n 的矩阵 A，对于有向网：

• 矩阵中的元素 (A[i][j]) 表示从顶点 i 到顶点 j 的有向边的权值。
  • 如果没有从顶点 i 到顶点 j 的边，则 (A[i][j]) 可以被赋值为无穷大（一般用极大整数表示）或者一个特殊值（如 null 或 -1），表示不存在路径或无法到达。

对于无向网：

• 矩阵仍然是对称的，即如果顶点 i 和顶点 j 之间存在一条无向边且带有一个权值 w，那么 (A[i][j] = A[j][i] = w)。

举例来说，假设有一个无向网，其中有三条边连接着三个顶点，并且边的权值分别为：(顶点1, 顶点2) 权重为3，(顶点1, 顶点3) 权重为5，(顶点2, 顶点3) 权重为1，则对应的邻接矩阵可能是：

| 0   3   5 |
| 3   0   1 |
| 5   1   0 |

通过邻接矩阵，我们可以直观地看出任意两点间的直接连通性和权值大小，便于进行诸如最短路径计算等图算法的操作。

邻接矩阵表示法的优缺点

优点：

• 直观、简单、好理解
• 方便检查任意一对顶点间是否存在边
• 方便找任一顶点的所有“邻接点”(有边直接相连的顶点)
• 方便计算任一顶点的“度”。

缺点：

• 不便于增加和删除顶点
• 浪费空间——存稀疏图(点很多而边很少)有大量无效元素
• 对稠密图(特别是完全图)还是很合算的
• 浪费时间——统计稀疏图中一共有多少条边