第 21 篇 的树是一对多分支；图则允许任意顶点之间连边——社交网络、路由表、任务依赖、编译单元关系，本质都是图。BFS 找最短、DFS 探路径、Dijkstra 算权重、拓扑排序排依赖——四大经典算法覆盖 90% 的工程场景。

demo：ref/cpp_demo/algorithms/graph/（graph.h、bfs、dfs、dijkstra、topological_sort）。

这是「现代 C++ 实战」系列的第 22 篇。建议先读 第 21 篇：树结构全家桶。

一、图的两种表示

顶点 V、边 E。两种存储方式，时空权衡不同：

表示 空间 查边 遍历邻居 适用
邻接矩阵 O(V²) O(1) O(V) 稠密图、频繁查边
邻接表 O(V+E) O(度) O(度) 稀疏图、遍历为主 
1
2
3
4
5
6
邻接矩阵（6 顶点）          邻接表
    0 1 2 3 4 5              0 → [1, 2]
0 [ 0 1 1 0 0 0 ]           1 → [3]
1 [ 0 0 0 1 0 0 ]           2 → [3, 4]
2 [ 0 0 0 1 1 0 ]           ...
...                         5 → []

demo 的 graph.h 同时维护两种结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Graph {
    int V;
    std::vector<std::list<int>> adj;           // 邻接表
    std::vector<std::vector<int>> adjMatrix;    // 邻接矩阵
public:
    Graph(int vertices) : V(vertices) {
        adj.resize(V);
        adjMatrix.resize(V, std::vector<int>(V, 0));
    }
    void addEdge(int v, int w) {
        adj[v].push_back(w);
        adjMatrix[v][w] = 1;
    }
};

有向图只加单向边；无向图双向各加一条。带权图在邻接表中存 pair<邻居, 权重>。

二、BFS：层序扩展，无权最短路径

广度优先搜索——用 std::queue，先访问近的、再访问远的，像水波扩散：

1
2
3
4
5
6
7
8
从 0 出发：          层序
  0                   L0: 0
 / \                  L1: 1, 2
1   2                 L2: 3
    |                 L3: 4
    3                 L4: 5
   / \
  4   5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void BFS(const Graph& g, int start) {
    std::vector<bool> visited(g.getV(), false);
    std::queue<int> q;
    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int v = q.front(); q.pop();
        // 处理 v ...
        for (int neighbor : g.getAdjList()[v]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

关键性质：边权均为 1 时，BFS 第一次到达某顶点的路径即为最短路径。

复杂度 值
时间 O(V + E)
空间 O(V)

应用：迷宫最短路、社交网络「六度分隔」、广播路由、Web 爬虫层级抓取。

三、DFS：深入到底，回溯与连通性

深度优先搜索——用 std::stack（或递归），一路走到底再回退：

1
2
3
4
5
从 0 出发（栈）：     访问顺序取决于压栈顺序
push 0 → pop 0       demo 逆序压邻居 → 0 1 2 4 5 3
push 2,1
pop 1 → push 3
...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void DFS(const Graph& g, int start) {
    std::vector<bool> visited(g.getV(), false);
    std::stack<int> s;
    s.push(start);

    while (!s.empty()) {
        int v = s.top(); s.pop();
        if (!visited[v]) {
            visited[v] = true;
            for (auto it = g.getAdjList()[v].rbegin();
                 it != g.getAdjList()[v].rend(); ++it) {
                if (!visited[*it]) s.push(*it);
            }
        }
    }
}

递归写法更简洁，但深图可能栈溢出——工程上迭代 + 显式栈更安全。

应用：

  • 连通分量：对每个未访问顶点 DFS，计数分量数
  • 环检测：DFS 中遇到已访问且在递归栈中的节点
  • 拓扑排序：DFS 后序逆序输出
  • 回溯：全排列、N 皇后、数独
复杂度 值
时间 O(V + E)
空间 O(V)

四、Dijkstra：带权最短路径

BFS 处理不了边权不同的情况。Dijkstra 用最小堆（std::priority_queue + std::greater）每次取当前距离最小的顶点，松弛邻居：

1
2
松弛：if dist[v] > dist[u] + weight(u,v)
         dist[v] = dist[u] + weight(u,v)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void dijkstra(int src) {
    std::vector<int> dist(V, INT_MAX);
    using P = std::pair<int,int>;  // {距离, 顶点}
    std::priority_queue<P, std::vector<P>, std::greater<P>> pq;

    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;  // 过期条目，跳过

        for (auto& [v, w] : adj[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

demo 从顶点 0 出发的距离：0→0, 1→3, 2→2, 3→5, 4→7, 5→13。

复杂度 值 前提
时间 O((V+E) log V) 非负权边
空间 O(V)

注意：负权边需 Bellman-Ford；全源最短路径稠密图可用 Floyd-Warshall O(V³)。

应用：地图导航、网络路由 OSPF、游戏 AI 寻路（配合 A* 启发式）。

五、拓扑排序：有向无环图的线性序

任务 A 依赖 B、B 依赖 C——编译顺序、Makefile 依赖、课程选修，都是拓扑排序问题。前提：有向无环图（DAG）。

方法一：DFS 后序

DFS 完成一个节点后压栈，最终出栈顺序即拓扑序。用 recStack 检测环：

1
2
3
4
5
6
7
8
9
10
11
12
13
bool topologicalSortUtil(int v, std::vector<bool>& visited,
                       std::vector<bool>& recStack, std::stack<int>& st) {
    visited[v] = true;
    recStack[v] = true;
    for (int nb : adj[v]) {
        if (!visited[nb]) {
            if (topologicalSortUtil(nb, visited, recStack, st)) return true;
        } else if (recStack[nb]) return true;  // 回边 → 有环
    }
    recStack[v] = false;
    st.push(v);
    return false;
}

方法二：Kahn 算法（BFS 变体）

  1. 统计每个顶点入度
  2. 入度为 0 的入队
  3. 出队时将其邻居入度 −1，新入度为 0 的继续入队
  4. 出队数 < V → 有环
1
2
边: 5→2, 5→0, 4→0, 4→1, 2→3, 3→1
入度为 0: 4, 5 → 拓扑序之一: 5 2 3 1 4 0
复杂度 值
时间 O(V + E)
空间 O(V)

六、四大算法选型

问题 算法 原因
无权最短路 BFS 层序保证最短
遍历 / 连通 / 回溯 DFS 深入探索
非负权最短路 Dijkstra 贪心 + 堆
任务依赖排序 拓扑排序 DAG 线性化
负权边最短路 Bellman-Ford 允许负权
全源最短路 Floyd-Warshall 实现简单，V 较小

七、运行 4 个 demo

1
2
3
4
5
cd ref/cpp_demo/algorithms/graph
g++ -std=c++17 -o bfs bfs.cpp && ./bfs
g++ -std=c++17 -o dfs dfs.cpp && ./dfs
g++ -std=c++17 -o dijkstra dijkstra.cpp && ./dijkstra
g++ -std=c++17 -o topological_sort topological_sort.cpp && ./topological_sort
demo 预期输出要点
bfs 从 0：0 1 2 3 4 5
dfs 从 0：0 1 3 5 4 2（栈顺序相关）
dijkstra 到各点距离：0, 3, 2, 5, 7, 13
topological_sort 之一：5 2 3 1 4 0

八、与 STL 的衔接

STL 容器 在图算法中的角色
std::vector<list<int>> 邻接表
std::queue BFS、Kahn 拓扑
std::stack DFS、DFS 拓扑
std::priority_queue Dijkstra 最小堆
std::vector<bool> 访问标记

第 20 篇 的栈与队列、第 21 篇 的堆，在这里组合成完整图算法工具箱。

九、小结

要点 内容
表示 邻接矩阵查边快，邻接表省空间
BFS 队列层序，无权最短路
DFS 栈/递归深入，连通、回溯、环检测
Dijkstra 最小堆 + 松弛，非负权最短路
拓扑排序 DAG 依赖排序，DFS 后序或 Kahn

下一篇进入字符串搜索与动态规划：KMP、Boyer-Moore、背包与 LCS——见 第 23 篇：字符串搜索与动态规划（计划）。