第 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 同时维护两种结构（bfs、dfs 使用；dijkstra、topological_sort 各自在 .cpp 里另定义了 WeightedGraph、TopologicalGraph）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
    }
    int getV() const { return V; }
    const std::vector<std::list<int>>& getAdjList() const { return adj; }
    const std::vector<std::vector<int>>& getAdjMatrix() const { return adjMatrix; }
};

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

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

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

demo 的有向图边为 0→1, 0→2, 1→3, 2→3, 2→4, 3→4, 3→5, 4→5，BFS 树与层序如下：

1
2
3
4
5
6
7
8
从 0 出发：          层序
    0                 L0: 0
   / \                L1: 1, 2
  1   2               L2: 3, 4
  |   |               L3: 5
  3   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 3 4 5 2
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)

demo 的 WeightedGraph 用 std::vector<std::list<std::pair<int, int>>> 存 {邻居, 权重}，addEdge 双向加边（无向图）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void dijkstra(int src) {
    std::vector<int> dist(V, INT_MAX);
    std::priority_queue<std::pair<int, int>,
                        std::vector<std::pair<int, int>>,
                        std::greater<std::pair<int, int>>> pq;  // {距离, 顶点}

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

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        for (auto& neighbor : adj[u]) {
            int v = neighbor.first;
            int weight = neighbor.second;
            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
}

demo 没有跳过堆里的过期条目（结果仍正确，只是多做几次无效松弛）；工程上常先取出 d = pq.top().first，再加 if (d > dist[u]) continue;。

demo 的边为 0-1(4), 0-2(3), 1-2(1), 1-3(2), 2-3(4), 3-4(2), 4-5(6)，从顶点 0 出发的距离：0→0, 1→4, 2→3, 3→6, 4→8, 5→14。

复杂度 值 前提
时间 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 检测环（demo TopologicalGraph 的私有函数，demo 只实现了这一种方法）：

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>& Stack) {
    visited[v] = true;
    recStack[v] = true;
    for (int nb : adj[v]) {
        if (!visited[nb]) {
            if (topologicalSortUtil(nb, visited, recStack, Stack)) return true;
        } else if (recStack[nb]) return true;  // 回边 → 有环
    }
    recStack[v] = false;
    Stack.push(v);
    return false;
}

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

  1. 统计每个顶点入度
  2. 入度为 0 的入队
  3. 出队时将其邻居入度 −1，新入度为 0 的继续入队
  4. 出队数 < V → 有环
1
2
3
边: 5→2, 5→0, 4→0, 4→1, 2→3, 3→1
入度为 0: 4, 5 → Kahn（按编号入队）得到: 4 5 2 0 3 1
                  demo 的 DFS 后序版得到: 5 4 2 3 1 0
复杂度 值
时间 O(V + E)
空间 O(V)

六、四大算法选型

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

七、运行 4 个 demo

每个 .cpp 编译为同名可执行文件（CMake 中按 C++11 构建）：

1
2
3
cd ref/cpp_demo/algorithms/graph
./build.sh --run              # 依次运行 4 个程序
./build.sh --run dijkstra     # 只运行一个（bfs / dfs / topological_sort 同理）
demo 预期输出要点
bfs 从 0：0 1 2 3 4 5
dfs 从 0：0 1 3 4 5 2（栈顺序相关）
dijkstra 到各点距离：0, 4, 3, 6, 8, 14
topological_sort 5 4 2 3 1 0

八、与 STL 的衔接

STL 容器 在图算法中的角色
std::vector<std::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 篇：字符串搜索与动态规划。