第6章：图论（Graph Theory）

一、导读

6.1 本章学习目标

图是计算机科学中最强大的建模工具之一。从社交网络到交通路线，从电路板设计到互联网路由， countless 的现实问题都可以用图来描述。本章将带你进入图论的世界，学习图的表示方法、遍历算法和最短路算法。

本章的核心学习目标包括：

掌握图的存储方式：邻接矩阵适合稠密图，邻接表适合稀疏图，理解各自的空间和时间复杂度。
深入理解 DFS 和 BFS：深度优先搜索和广度优先搜索是图算法的两大基石。
掌握 Dijkstra 最短路算法：单源最短路（非负权），使用优先队列优化到 O((V+E)logV)。
了解 Floyd 全源最短路：O(V³) 的算法，适用于小规模图或多源查询。
学会最小生成树算法：Kruskal 和 Prim 算法，理解贪心在其中的应用。
掌握拓扑排序：DAG 上的线性排序，用于任务调度和依赖关系分析。

6.2 为什么本章如此重要

图论在算法竞赛中的地位举足轻重。历年竞赛题目中，图论相关的题目占比超过 20%，而且难度跨度大——从基础的 BFS/DFS 到复杂的最短路、网络流，图论几乎覆盖了竞赛的所有难度层次。

更重要的是，图论是建模能力的最佳训练场。很多题目不会直接告诉你"这是一道图论题"，你需要自己识别出问题中的"顶点"和"边"，将问题转化为图论模型。这种抽象能力是算法竞赛的核心竞争力。

DFS 和 BFS 不仅是图论的基础，也是后续学习树论、搜索算法、动态规划（状态空间搜索）的必备工具。Dijkstra 算法则展示了贪心策略和优先队列的强大组合——这种模式在竞赛中反复出现。

6.3 核心问题引导

在阅读本章时，请带着以下问题思考：

邻接矩阵和邻接表各适合什么场景？如何选择？

DFS 和 BFS 在图的遍历中有什么本质区别？它们各自能解决什么问题？

Dijkstra 算法为什么不能处理负权边？负权边会导致什么问题？

最小生成树的"贪心选择"为什么是正确的？如何证明？

拓扑排序能检测环吗？如何利用拓扑排序判断有向图中是否有环？

如何将一个现实问题抽象为图论模型？关键步骤是什么？

二、核心概念详解

6.1 图的表示

6.1.1 邻接矩阵

用一个 n×n 的二维数组表示图，matrix[i][j] 表示顶点 i 到 j 的边的权值（或是否存在边）：

cpp

const int INF = 1e9;
int matrix[1005][1005];
int n, m;

void init() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            matrix[i][j] = (i == j) ? 0 : INF;
}

void add_edge(int u, int v, int w) {
    matrix[u][v] = w;
    // matrix[v][u] = w;  // 无向图需要双向加边
}

复杂度：空间 O(V²)，建图 O(V²)，查询边 O(1)。适合稠密图（边数接近 V²）。

6.1.2 邻接表

为每个顶点维护一个链表（或 vector），存储与它相邻的边：

cpp

struct Edge { int to, w; };
vector<Edge> adj[100005];
int n, m;

void add_edge(int u, int v, int w) {
    adj[u].push_back({v, w});
    // adj[v].push_back({u, w});  // 无向图
}

复杂度：空间 O(V+E)，建图 O(E)，遍历邻居 O(degree)。适合稀疏图（边数远小于 V²）。

6.1.3 选择策略

特征	邻接矩阵	邻接表
空间	O(V²)	O(V+E)
查询边	O(1)	O(degree)
遍历邻居	O(V)	O(degree)
适合场景	稠密图、Floyd	Dijkstra、BFS、DFS

6.2 深度优先搜索（DFS）

6.2.1 DFS 的原理

DFS 从起点出发，沿着一条路径尽可能深入地走，直到走不动为止，然后回溯到上一个分叉点，选择另一条路继续深入。这个过程天然适合用递归实现：

cpp

bool visited[100005];
vector<int> adj[100005];

void dfs(int u) {
    visited[u] = true;
    printf("Visit %d\n", u);
    for (int v : adj[u]) {
        if (!visited[v])
            dfs(v);
    }
}

6.2.2 DFS 的应用：连通性检测

cpp

int component[100005], comp_cnt = 0;

void dfs(int u, int comp_id) {
    component[u] = comp_id;
    for (int v : adj[u]) {
        if (component[v] == 0)
            dfs(v, comp_id);
    }
}

int count_components(int n) {
    memset(component, 0, sizeof(component));
    comp_cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (component[i] == 0) {
            comp_cnt++;
            dfs(i, comp_cnt);
        }
    }
    return comp_cnt;
}

6.2.3 DFS 检测环

cpp

int color[100005];  // 0=未访问, 1=正在访问, 2=已完成
bool has_cycle = false;

void dfs(int u, int parent) {
    color[u] = 1;
    for (int v : adj[u]) {
        if (v == parent) continue;
        if (color[v] == 1) { has_cycle = true; return; }
        if (color[v] == 0) dfs(v, u);
    }
    color[u] = 2;
}

6.3 广度优先搜索（BFS）

6.3.1 BFS 的原理

BFS 从起点出发，先访问所有距离为 1 的邻居，再访问距离为 2 的邻居，以此类推。它像水波一样一层一层地扩散，天然使用队列实现：

cpp

int dist[100005];

void bfs(int start, int n) {
    for (int i = 1; i <= n; i++) dist[i] = -1;
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

BFS 的核心性质：在无权图中，BFS 找到的路径一定是最短路径。

6.3.2 BFS vs DFS

特征	BFS	DFS
数据结构	队列	栈（递归）
遍历顺序	逐层扩展	纵深推进
最短路	无权图最短路	不保证最短
空间复杂度	O(V)（队列）	O(V)（栈）
适用场景	最短路、层次遍历	连通性、拓扑排序、回溯

6.4 Dijkstra 最短路算法

6.4.1 算法思想

Dijkstra 算法解决单源最短路问题：给定起点 s，求 s 到所有其他顶点的最短距离。要求图中没有负权边。

算法采用贪心策略：

维护一个集合 S，包含已确定最短距离的顶点

每次从"未确定"的顶点中，选择距离起点最近的顶点 u，加入 S

用 u 更新其邻居的最短距离

重复直到所有顶点都加入 S

6.4.2 优先队列优化

朴素 Dijkstra 的时间复杂度是 O(V²)，使用优先队列可以优化到 O((V+E)logV)：

cpp

const int INF = 1e9;
struct Edge { int to, w; };
vector<Edge> adj[100005];
int dist[100005];
int n, m;

void dijkstra(int s) {
    for (int i = 1; i <= n; i++) dist[i] = INF;
    dist[s] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0, s});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;  // 过时信息，忽略
        for (auto &e : adj[u]) {
            if (dist[u] + e.w < dist[e.to]) {
                dist[e.to] = dist[u] + e.w;
                pq.push({dist[e.to], e.to});
            }
        }
    }
}

关键细节：

if (d > dist[u]) continue; 这行很重要——优先队列中可能有过时的信息（某个顶点的最短距离已经被更新得更小了），需要跳过
使用 pair<int,int> 存储 (距离, 顶点编号)，优先队列按距离从小到大排序

6.4.3 路径还原

cpp

int prev_node[100005];

// 在 dijkstra 中记录前驱
void dijkstra_with_path(int s) {
    // ... 同上 ...
    for (auto &e : adj[u]) {
        if (dist[u] + e.w < dist[e.to]) {
            dist[e.to] = dist[u] + e.w;
            prev_node[e.to] = u;  // 记录前驱
            pq.push({dist[e.to], e.to});
        }
    }
}

// 还原从 s 到 t 的路径
void print_path(int t) {
    vector<int> path;
    for (int v = t; v != -1; v = prev_node[v])
        path.push_back(v);
    reverse(path.begin(), path.end());
    for (int i = 0; i < (int)path.size(); i++)
        printf("%d%c", path[i], " \n"[i == (int)path.size() - 1]);
}

6.5 Floyd 全源最短路

6.5.1 算法思想

Floyd 算法求所有顶点对之间的最短距离。基于动态规划：

设 dist[k][i][j] 表示只经过顶点 {1, 2, ..., k} 时，从 i 到 j 的最短距离。状态转移：

dist[k][i][j] = min(dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j])

由于第 k 层只依赖第 k-1 层，可以压缩为一维：

cpp

int dist[505][505];
int n;

void floyd() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

复杂度：时间 O(V³)，空间 O(V²)。适合 V ≤ 500 的小规模图。

6.6 最小生成树

6.6.1 Kruskal 算法

Kruskal 算法基于贪心：将所有边按权值排序，从小到大依次加入，如果不形成环就保留，否则跳过。使用并查集判断环：

cpp

struct Edge { int u, v, w; };
vector<Edge> edges;
int parent[100005];

int find(int x) {
    return parent[x] == x ? x : parent[x] = find(parent[x]);
}

bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    parent[x] = y;
    return true;
}

int kruskal(int n) {
    sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) {
        return a.w < b.w;
    });
    for (int i = 1; i <= n; i++) parent[i] = i;
    
    int total = 0, cnt = 0;
    for (auto &e : edges) {
        if (unite(e.u, e.v)) {
            total += e.w;
            cnt++;
            if (cnt == n - 1) break;
        }
    }
    return total;
}

复杂度：排序 O(E log E)，并查集操作 O(E α(V))，总复杂度 O(E log E)。

6.7 拓扑排序

6.7.1 原理

拓扑排序是 DAG（有向无环图）上的一种线性排序，使得对于每条边 (u, v)，u 都排在 v 前面。

BFS 实现（Kahn 算法）：

cpp

int in_degree[100005];
vector<int> adj[100005];
int n;

vector<int> topo_sort() {
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (in_degree[i] == 0) q.push(i);
    
    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            if (--in_degree[v] == 0)
                q.push(v);
        }
    }
    return order;  // 如果 order.size() < n，说明有环
}

三、实战案例

3.1 案例一：Dijkstra 应用——信使

问题描述：n 个哨所，m 条双向道路。从总部（哨所 1）出发，求命令传达到所有哨所的最短时间（即求 1 到所有点的最短距离的最大值）。

cpp

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = 1e9;
struct Edge { int to, w; };
vector<Edge> adj[105];
int dist[105];
int n, m;

void dijkstra(int s) {
    for (int i = 1; i <= n; i++) dist[i] = INF;
    dist[s] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto &e : adj[u]) {
            if (dist[u] + e.w < dist[e.to]) {
                dist[e.to] = dist[u] + e.w;
                pq.push({dist[e.to], e.to});
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    dijkstra(1);
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, dist[i]);
    printf("%d\n", ans == INF ? -1 : ans);
    return 0;
}

3.2 案例二：BFS 应用——迷宫最短路

cpp

#include <cstdio>
#include <queue>
using namespace std;

int maze[105][105], dist[105][105];
int n, m;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int bfs(int sx, int sy, int tx, int ty) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            dist[i][j] = -1;
    
    queue<pair<int,int>> q;
    dist[sx][sy] = 0;
    q.push({sx, sy});
    
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        if (x == tx && y == ty) return dist[x][y];
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m
                && maze[nx][ny] == 0 && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    return -1;
}

四、本章小结

本章系统介绍了图论的基础知识和经典算法：

图的表示：邻接矩阵适合稠密图，邻接表适合稀疏图。

DFS：纵深推进，用于连通性检测、环检测、拓扑排序。

BFS：逐层扩展，用于无权图最短路、层次遍历。

Dijkstra：单源最短路（非负权），优先队列优化 O((V+E)logV)。

Floyd：全源最短路，O(V³)，适合小规模图。

Kruskal：最小生成树，贪心+并查集，O(E log E)。

拓扑排序：DAG 的线性排序，Kahn 算法基于 BFS。

图论的核心能力是建模——将现实问题抽象为顶点和边，然后选择合适的算法。这种能力需要大量的练习来培养。

五、思考与练习

思考题

为什么 Dijkstra 不能处理负权边？Bellman-Ford 算法是如何解决这个问题的？

如何用 DFS 实现拓扑排序？与 BFS 实现的拓扑排序有什么区别？

Kruskal 和 Prim 算法的贪心策略有什么不同？各自适合什么场景？

如何判断一个有向图是否是强连通的？

编程练习

最短路计数：求从 s 到 t 的最短路径条数。

最小生成树唯一性：判断一个图的最小生成树是否唯一。

有向图的强连通分量：使用 Tarjan 算法求 SCC。

差分约束系统：将不等式组转化为最短路问题求解。