图的存储：邻接表 (Adjacency List) 详解

1. 什么是邻接表？

邻接表是图的一种链式存储结构。它克服了邻接矩阵在稀疏图（边数远小于顶点数平方）中浪费空间的缺点。

基本思想：
对于图中的每个顶点 $v$，我们将所有与 $v$ 邻接的顶点记录在一个列表中。

  • 通常使用数组（或 vector）来索引所有顶点。
  • 数组的每个元素不再是一个单一的值，而是一个容器（链表或 vector），存储该顶点的所有出边。

内存模型示意

假设有 4 个顶点，边为 $1\to2, 1\to3, 2\to4$。

AdjList (Array/Vector)
+---+
| 1 | -> [2] -> [3] (顶点1连接到2和3)
+---+
| 2 | -> [4] (顶点2连接到4)
+---+
| 3 | -> NULL (顶点3无出边)
+---+
| 4 | -> NULL (顶点4无出边)
+---+

2. 数据结构定义 (C++)

在 C++ 中，最现代且方便的实现方式是使用 STL 的 std::vector。

2.1 无权图 (Unweighted Graph)

如果边没有权值，只需要存储目标顶点即可。

C++

1
2
3
4
5
6
#include <vector>
using namespace std;

// N 是顶点数量，通常开大一点或根据输入动态设定
// G[u] 是一个 vector，存储了 u 指向的所有顶点
vector<vector<int>> G;

2.2 带权图 (Weighted Graph)

如果边有权值（例如距离、费用），我们需要同时存储目标点和权值。推荐使用 struct 或 pair。

方式 A：使用 Struct (推荐，代码清晰)

C++

1
2
3
4
5
6
struct Edge {
    int to;     // 目标顶点
    int weight; // 权值
};

vector<vector<Edge>> G;

方式 B：使用 Pair (写起来快，但可读性稍差)

C++

1
2
// pair.first = 目标点, pair.second = 权值
vector<vector<pair<int, int>>> G;

3. 核心操作详解

以下代码示例假设我们要处理一个包含 n 个顶点的图（编号 1 到 n）。

3.1 初始化 (Initialization)

在使用之前，必须初始化外层 vector 的大小。

C++

1
2
3
int n = 5; // 假设有5个点
// 初始化大小为 n + 1，以便我们可以直接使用 G[1] 到 G[n]
vector<vector<int>> G(n + 1);

3.2 插入边 (Insertion)

这是最常用的操作，时间复杂度为 $O(1)$。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 添加一条从 u 到 v 的边
void addEdge(vector<vector<int>>& G, int u, int v, bool isDirected) {
    G[u].push_back(v);
    
    // 如果是无向图，还需要添加反向边
    if (!isDirected) {
        G[v].push_back(u);
    }
}

// 带权图版本
void addWeightedEdge(vector<vector<Edge>>& G, int u, int v, int w, bool isDirected) {
    G[u].push_back({v, w});
    if (!isDirected) {
        G[v].push_back({u, w});
    }
}

3.3 删除边 (Deletion)

在 vector 实现的邻接表中，删除边比邻接矩阵稍微麻烦一些，因为需要遍历链表找到目标并删除。

  • 时间复杂度：$O(k)$，其中 $k$ 是顶点 $u$ 的度数（邻居数量）。

C++

1
2
3
4
5
6
7
8
9
10
11
// 删除从 u 到 v 的边
void removeEdge(vector<vector<int>>& G, int u, int v) {
    // 遍历 u 的邻居列表
    for (int i = 0; i < G[u].size(); i++) {
        if (G[u][i] == v) {
            // 找到 v 了，删除它
            G[u].erase(G[u].begin() + i); 
            break; // 删除后立即退出，防止迭代器失效或重复删除
        }
    }
}

优化技巧 (Swap and Pop)：

如果邻居的顺序不重要，可以使用“与最后一个元素交换，然后删除末尾”的方法，将删除操作降为 $O(1)$。

C++

1
2
3
4
5
if (G[u][i] == v) {
    swap(G[u][i], G[u].back());
    G[u].pop_back();
    break;
}

4. 图的遍历 (Traversal)

这是图论算法的基石。

4.1 深度优先搜索 (DFS)

类似于树的先序遍历，一条路走到黑，撞墙了再回溯。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<bool> visited; // 记录访问状态，防止死循环

void dfs(int u, const vector<vector<int>>& G) {
    visited[u] = true;
    printf("访问了: %d\n", u);

    // 遍历 u 的所有邻居 v
    for (int v : G[u]) {
        if (!visited[v]) {
            dfs(v, G); // 递归访问
        }
    }
}

// 调用入口
// visited.assign(n + 1, false);
// dfs(1, G);

4.2 广度优先搜索 (BFS)

类似于树的层序遍历，像水波纹一样一层层扩散。常用于求无权图的最短路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <queue>

void bfs(int start, const vector<vector<int>>& G, int n) {
    vector<bool> visited(n + 1, false);
    queue<int> q;

    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        printf("访问了: %d\n", u);

        // 遍历 u 的所有邻居
        for (int v : G[u]) {
            if (!visited[v]) {
                visited[v] = true;  // 入队时标记，防止重复入队
                q.push(v);
            }
        }
    }
}

5. 邻接表 vs 邻接矩阵：总结

特性 邻接表 (vector) 邻接矩阵 (int G[][])
空间复杂度 $O(V + E)$ (省空间) $O(V^2)$ (浪费空间)
判断两点是否相连 $O(Degree(V))$ (较慢) $O(1)$ (极快)
添加边 $O(1)$ $O(1)$
删除边 $O(Degree(V))$ $O(1)$
遍历某点的邻居 $O(Degree(V))$ (极快) $O(V)$ (慢，需扫描整行)
适用场景 稀疏图 (绝大多数工程/算法题) 稠密图 (边数接近 $V^2$)

何时选择邻接表？

  1. 图很大：如 $V > 5000$。

  2. 图很稀疏：边数 $E$ 没有接近 $V^2$。

  3. 算法需要遍历邻居：如 DFS, BFS, Dijkstra, Prim。

何时选择邻接矩阵？

  1. 图很小：如 $V \le 1000$。

  2. 图极其稠密：也就是大部分点之间都有边。

  3. 算法需要频繁查询任意两点是否有边：如 Floyd 算法。