在数据结构中，图是一种由顶点（Vertex）和边（Edge）组成的数据结构。表示图的方法有很多，比如邻接表、邻接矩阵等。其中，邻接矩阵是一种直观且基础的表示方式，尤其适合初学者理解。
一、什么是邻接矩阵？¶
邻接矩阵本质上是一个二维数组，用于表示图中顶点之间的连接关系。它的核心思想是：用矩阵的行和列分别对应图的顶点，矩阵中的元素值表示两个顶点之间是否存在边，以及边的权重（如果有权重）。
1. 基本定义¶
假设图有 n 个顶点，我们将顶点编号为 0, 1, 2, ..., n-1。邻接矩阵是一个 n×n 的二维数组 adj，其中：
- 若 adj[i][j] = 1（或具体权重值），表示顶点 i 和顶点 j 之间存在一条边；
- 若 adj[i][j] = 0（或无穷大 ∞），表示顶点 i 和顶点 j 之间不存在边（对于有权图，∞ 表示无直接边）。
2. 示例：无向图的邻接矩阵¶
假设有一个无向图，顶点为 A, B, C, D（编号 0, 1, 2, 3），边为 A-B, B-C, C-D, D-A。其邻接矩阵如下：
| A(0) | B(1) | C(2) | D(3) | |
|---|---|---|---|---|
| A(0) | 0 | 1 | 0 | 1 |
| B(1) | 1 | 0 | 1 | 0 |
| C(2) | 0 | 1 | 0 | 1 |
| D(3) | 1 | 0 | 1 | 0 |
- 例如：
adj[0][1] = 1表示顶点A和B之间有边；adj[0][2] = 0表示A和C之间没有边。
二、邻接矩阵的优点¶
-
快速判断边是否存在
要判断顶点i和j之间是否有边，只需直接访问adj[i][j]，时间复杂度为 O(1)。例如，在邻接表中可能需要遍历链表查找，而邻接矩阵无需遍历，直接通过索引定位。 -
计算顶点度高效
- 无向图：顶点i的度（与其他顶点相连的边数）等于邻接矩阵第i行的元素之和（因为无向图中边(i,j)同时出现在i行和j列）。
- 有向图：顶点i的出度（从i出发的边数）是第i行的和，入度（指向i的边数）是第i列的和。 -
适合稠密图
若图中边数较多（接近n²，即顶点数的平方），邻接矩阵的空间利用率高。例如，一个完全图（任意两个顶点都有边）的邻接矩阵会被完全填满，此时邻接表反而可能因额外存储信息而浪费空间。 -
实现简单
对于初学者，邻接矩阵的数组结构直观易懂，无需复杂的数据结构（如链表或指针），容易理解和编码。
三、邻接矩阵的缺点¶
-
空间效率低
邻接矩阵需要n×n的空间，对于 稀疏图（边数远小于n²的图），会造成大量空间浪费。例如，一个有 1000 个顶点、仅 100 条边的稀疏图，邻接矩阵需要1000×1000 = 1000000个元素，而邻接表仅需存储 100 条边的信息，空间优势明显。 -
遍历邻接顶点效率低
要遍历顶点i的所有邻接顶点，需遍历邻接矩阵的第i行（或列），时间复杂度为 O(n)。例如，顶点A有 4 个邻接顶点，在邻接矩阵中需要遍历 4 个顶点才能找到所有邻居，而在邻接表中只需直接访问链表即可，时间复杂度为 O(度)（度通常远小于n）。 -
不适合动态调整边数
当图的边数频繁变化（如插入或删除边）时，邻接矩阵需要修改数组元素，虽然修改单个元素是 O(1)，但对于大规模图的动态操作，整体效率仍不如邻接表灵活。
四、总结¶
邻接矩阵的核心特点是以空间换时间：
- 适合场景：稠密图（边数多）、需要频繁查询边是否存在、或计算顶点度的场景。
- 不适合场景：稀疏图（边数少）、需要频繁遍历邻接顶点的场景。
对于初学者而言，邻接矩阵是理解图的基础工具，通过它可以快速掌握图的基本连接关系。但在实际应用中，需根据图的类型（稠密/稀疏）选择合适的表示方法。