Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

第五十八 图论

图论（Graph Theory）是数学和计算机科学的重要分支，研究由**顶点（Vertex）和边（Edge）**构成的图结构。从社交网络到地图导航，从互联网路由到芯片布线，图论无处不在。1736 年，欧拉解决了哥尼斯堡七桥问题，标志着图论的诞生。

一、图的基本概念

1.1 图的定义

图 $G = (V, E)$ 由顶点集 $V$ 和边集 $E$ 组成。

术语说明
有向图边有方向，$(u,v) \neq (v,u)$
无向图边无方向，$(u,v) = (v,u)$
加权图每条边有权重 $w(u,v)$
简单图无自环、无重边
完全图任意两顶点间都有边，$K_n$ 有 $\frac{n(n-1)}{2}$ 条边
二分图顶点可分为两组，边只连接不同组的顶点
DAG有向无环图（Directed Acyclic Graph）

1.2 度与路径

术语说明
度（Degree）与顶点相连的边数；有向图分入度和出度
路径顶点序列 $v_1, v_2, \ldots, v_k$，相邻顶点间有边
环（Cycle）起点和终点相同的路径
连通图任意两顶点间都有路径
强连通有向图中任意两顶点互相可达

握手定理： 无向图所有顶点的度之和等于边数的两倍：$\sum_{v \in V} \deg(v) = 2|E|$。

二、图的表示

2.1 邻接矩阵

用 $n \times n$ 矩阵 $A$ 表示图，$A[i][j] = 1$（或权重）表示顶点 $i$ 和 $j$ 之间有边。

优点缺点
查询边是否存在 $O(1)$空间 $O(n^2)$，稀疏图浪费
适合稠密图遍历邻居 $O(n)$
 
#![allow(unused)]
fn main() {
struct AdjMatrix {
    n: usize,
    matrix: Vec<Vec<i64>>, // -1 表示无边
}

impl AdjMatrix {
    fn new(n: usize) -> Self {
        AdjMatrix {
            n,
            matrix: vec![vec![-1; n]; n],
        }
    }

    fn add_edge(&mut self, u: usize, v: usize, weight: i64) {
        self.matrix[u][v] = weight;
        self.matrix[v][u] = weight; // 无向图
    }
}
}

2.2 邻接表

每个顶点维护一个邻居列表。

优点缺点
空间 $O(n + m)$，适合稀疏图查询边 $O(\deg(v))$
遍历邻居高效
 
#![allow(unused)]
fn main() {
struct AdjList {
    n: usize,
    adj: Vec<Vec<(usize, i64)>>, // (邻居, 权重)
}

impl AdjList {
    fn new(n: usize) -> Self {
        AdjList {
            n,
            adj: vec![Vec::new(); n],
        }
    }

    fn add_edge(&mut self, u: usize, v: usize, weight: i64) {
        self.adj[u].push((v, weight));
        self.adj[v].push((u, weight)); // 无向图
    }
}
}

三、图的遍历

3.1 深度优先搜索（DFS）

DFS 沿一条路深入到底，再回溯。时间复杂度 $O(V + E)$。

#![allow(unused)]
fn main() {
fn dfs(adj: &[Vec<usize>], start: usize) -> Vec<usize> {
    let mut visited = vec![false; adj.len()];
    let mut order = Vec::new();
    dfs_visit(adj, start, &mut visited, &mut order);
    order
}

fn dfs_visit(adj: &[Vec<usize>], u: usize, visited: &mut Vec<bool>, order: &mut Vec<usize>) {
    visited[u] = true;
    order.push(u);
    for &v in &adj[u] {
        if !visited[v] {
            dfs_visit(adj, v, visited, order);
        }
    }
}
}

应用： 连通分量检测、环检测、拓扑排序、强连通分量（Tarjan 算法）。

3.2 广度优先搜索（BFS）

BFS 逐层扩展，适合求无权图的最短路径。时间复杂度 $O(V + E)$。

#![allow(unused)]
fn main() {
use std::collections::VecDeque;

fn bfs_shortest_path(adj: &[Vec<usize>], start: usize) -> Vec<i32> {
    let n = adj.len();
    let mut dist = vec![-1i32; n];
    let mut queue = VecDeque::new();
    dist[start] = 0;
    queue.push_back(start);

    while let Some(u) = queue.pop_front() {
        for &v in &adj[u] {
            if dist[v] == -1 {
                dist[v] = dist[u] + 1;
                queue.push_back(v);
            }
        }
    }
    dist
}
}

应用： 无权最短路径、层次遍历、社交网络“六度分隔“验证。

四、最短路径

4.1 Dijkstra 算法

求单源最短路径（边权非负）。时间复杂度 $O((V + E) \log V)$（优先队列实现）。

#![allow(unused)]
fn main() {
use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn dijkstra(adj: &[Vec<(usize, u64)>], start: usize) -> Vec<u64> {
    let n = adj.len();
    let mut dist = vec![u64::MAX; n];
    let mut heap = BinaryHeap::new();

    dist[start] = 0;
    heap.push(Reverse((0u64, start)));

    while let Some(Reverse((d, u))) = heap.pop() {
        if d > dist[u] { continue; } // 已过期的条目
        for &(v, w) in &adj[u] {
            let new_dist = dist[u] + w;
            if new_dist < dist[v] {
                dist[v] = new_dist;
                heap.push(Reverse((new_dist, v)));
            }
        }
    }
    dist
}
}
算法适用条件时间复杂度
Dijkstra非负权边$O((V+E)\log V)$
Bellman-Ford允许负权边$O(VE)$
Floyd-Warshall全源最短路径$O(V^3)$
SPFA队列优化的 Bellman-Ford平均 $O(E)$

4.2 Floyd-Warshall 全源最短路径

#![allow(unused)]
fn main() {
fn floyd_warshall(dist: &mut Vec<Vec<i64>>) {
    let n = dist.len();
    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                if dist[i][k] != i64::MAX && dist[k][j] != i64::MAX {
                    dist[i][j] = dist[i][j].min(dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}
}

五、最小生成树

**最小生成树（MST）**是连接图中所有顶点且边权之和最小的子图。

5.1 Kruskal 算法

按边权从小到大排序，用并查集判断是否形成环。时间复杂度 $O(E \log E)$。

#![allow(unused)]
fn main() {
struct UnionFind {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl UnionFind {
    fn new(n: usize) -> Self {
        UnionFind {
            parent: (0..n).collect(),
            rank: vec![0; n],
        }
    }

    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            self.parent[x] = self.find(self.parent[x]); // 路径压缩
        }
        self.parent[x]
    }

    fn union(&mut self, x: usize, y: usize) -> bool {
        let (rx, ry) = (self.find(x), self.find(y));
        if rx == ry { return false; }
        // 按秩合并
        match self.rank[rx].cmp(&self.rank[ry]) {
            std::cmp::Ordering::Less => self.parent[rx] = ry,
            std::cmp::Ordering::Greater => self.parent[ry] = rx,
            std::cmp::Ordering::Equal => {
                self.parent[ry] = rx;
                self.rank[rx] += 1;
            }
        }
        true
    }
}

fn kruskal(n: usize, edges: &mut Vec<(usize, usize, i64)>) -> i64 {
    edges.sort_by_key(|e| e.2);
    let mut uf = UnionFind::new(n);
    let mut total_weight = 0i64;

    for &(u, v, w) in edges.iter() {
        if uf.union(u, v) {
            total_weight += w;
        }
    }
    total_weight
}
}

5.2 Prim 算法

从一个顶点出发，逐步加入最小权边扩展生成树。时间复杂度 $O(E \log V)$（优先队列实现）。

算法适合场景时间复杂度
Kruskal稀疏图$O(E \log E)$
Prim稠密图$O(E \log V)$

六、拓扑排序

对**有向无环图（DAG）**的顶点进行排序，使得对每条有向边 $(u, v)$，$u$ 都排在 $v$ 前面。

Kahn 算法（BFS 实现）：

#![allow(unused)]
fn main() {
fn topological_sort(adj: &[Vec<usize>]) -> Option<Vec<usize>> {
    let n = adj.len();
    let mut in_degree = vec![0usize; n];
    for neighbors in adj {
        for &v in neighbors {
            in_degree[v] += 1;
        }
    }

    let mut queue: VecDeque<usize> = (0..n)
        .filter(|&i| in_degree[i] == 0)
        .collect();
    let mut order = Vec::with_capacity(n);

    while let Some(u) = queue.pop_front() {
        order.push(u);
        for &v in &adj[u] {
            in_degree[v] -= 1;
            if in_degree[v] == 0 {
                queue.push_back(v);
            }
        }
    }

    if order.len() == n { Some(order) } else { None } // 有环则返回 None
}
}

应用： 任务调度、课程先修关系、编译依赖分析、构建系统（如 Make、Cargo）。

七、网络流

7.1 最大流问题

给定有向图，每条边有容量限制，求从源点 $s$ 到汇点 $t$ 的最大流量。

Ford-Fulkerson 方法： 反复寻找增广路径，沿路径推送流量，直到无增广路径。

Edmonds-Karp 算法（BFS 实现）： 时间复杂度 $O(VE^2)$。

#![allow(unused)]
fn main() {
fn edmonds_karp(capacity: &mut Vec<Vec<i64>>, s: usize, t: usize) -> i64 {
    let n = capacity.len();
    let mut max_flow = 0i64;

    loop {
        // BFS 寻找增广路径
        let mut parent = vec![(-1i32, -1i32); n]; // (前驱节点, 瓶颈容量)
        let mut visited = vec![false; n];
        let mut queue = VecDeque::new();

        visited[s] = true;
        queue.push_back((s, i64::MAX));

        while let Some((u, flow)) = queue.pop_front() {
            if u == t {
                // 沿增广路径推送流量
                let mut v = t;
                while v != s {
                    let (p, _) = parent[v];
                    let p = p as usize;
                    capacity[p][v] -= flow;
                    capacity[v][p] += flow;
                    v = p;
                }
                max_flow += flow;
                break;
            }
            for v in 0..n {
                if !visited[v] && capacity[u][v] > 0 {
                    visited[v] = true;
                    parent[v] = (u as i32, 0);
                    queue.push_back((v, flow.min(capacity[u][v])));
                }
            }
        }

        if !visited[t] { break; } // 无增广路径
    }
    max_flow
}
}

7.2 最大流最小割定理

最大流等于最小割。 将图分为两部分的最小边权和等于最大流量。

应用说明
网络带宽通信网络的最大传输能力
二分图匹配最大匹配 = 最大流
项目选择利润最大化的项目组合
图像分割将图像分为前景和背景

八、图着色与经典问题

8.1 图着色问题

给图的顶点着色，使相邻顶点颜色不同。求最少颜色数（色数 $\chi(G)$）。

图的类型色数
空图1
二分图2
奇数环3
完全图 $K_n$$n$
平面图$\leq 4$（四色定理）

四色定理： 任何平面地图只需 4 种颜色即可着色，使得相邻区域颜色不同。1976 年由计算机辅助证明，是第一个被计算机证明的重要数学定理。

8.2 哥尼斯堡七桥问题

1736 年欧拉证明：哥尼斯堡的七座桥无法每条恰好走一次。

欧拉路径存在的条件：

  • 欧拉回路（起点 = 终点）：所有顶点度数为偶数
  • 欧拉路径（起点 ≠ 终点）：恰好 2 个顶点度数为奇数

8.3 旅行商问题（TSP）

经过所有顶点恰好一次并回到起点的最短回路。NP-hard 问题，是组合优化的经典难题。

九、图论在 Rust 生态中的应用

Crate功能
petgraph通用图数据结构与算法库
pathfindingA*、Dijkstra、BFS 等寻路算法
graphlib轻量级图库
▶ 在 Rust Explorer 中运行
/*
[dependencies]
petgraph = "0.6"
*/
use petgraph::graph::Graph;
use petgraph::algo::dijkstra;
use petgraph::visit::EdgeRef;

fn main() {
    let mut graph = Graph::<&str, f64>::new();
    let a = graph.add_node("北京");
    let b = graph.add_node("上海");
    let c = graph.add_node("广州");

    graph.add_edge(a, b, 1200.0);
    graph.add_edge(b, c, 1400.0);
    graph.add_edge(a, c, 2100.0);

    // Dijkstra 最短路径
    let distances = dijkstra(&graph, a, None, |e| *e.weight());
    println!("从北京到各城市的最短距离: {:?}", distances);
}

十、总结与练习

本章小结

知识点要点
图的表示邻接矩阵 $O(n^2)$ 适合稠密图，邻接表 $O(n+m)$ 适合稀疏图
DFS / BFS图遍历的两大基础算法，$O(V+E)$
Dijkstra非负权单源最短路径，$O((V+E)\log V)$
Floyd-Warshall全源最短路径，$O(V^3)$
最小生成树Kruskal（并查集）和 Prim（优先队列）
拓扑排序DAG 的线性排序，Kahn 算法
网络流最大流 = 最小割，Edmonds-Karp 算法
图着色四色定理，NP-hard 的一般图着色
欧拉路径所有顶点偶数度 → 欧拉回路

练习建议

  1. 图遍历：用 DFS 和 BFS 分别遍历一个给定的图，对比访问顺序，分析各自的适用场景。
  2. 最短路径：实现 Dijkstra 算法，求一个城市交通网中从起点到所有终点的最短距离。
  3. 最小生成树：用 Kruskal 算法为一个模拟的网络（如校园网布线）计算最优连接方案。
  4. 拓扑排序：模拟一个课程先修关系，用 Kahn 算法生成合法的修课顺序；加入环检测逻辑。
  5. 网络流：实现 Edmonds-Karp 算法，求解一个二分图最大匹配问题（如任务分配）。
  6. 社交网络分析：构建一个简单的社交网络图，用 BFS 验证“六度分隔“假说，计算任意两人之间的最短社交距离。