第16章图论基础

学习目标

掌握图的形式化定义与基本性质
理解图的多种表示方法及其复杂度分析
掌握图遍历算法的正确性证明
理解图的连通性与路径理论
掌握图ADT的代数规范

16.1 图的形式化定义

16.1.1 基本定义

定义 16.1（图） 图 $G$ 是一个二元组 $G = (V, E)$，其中：

$V$ 是有限非空顶点集（vertex set）
$E \subseteq V \times V$ 是边集（edge set）

定义 16.2（无向图） 无向图 $G = (V, E)$ 中，边是无序对：$e = {u, v}$，其中 $u, v \in V$，$u \neq v$。

定义 16.3（有向图） 有向图（digraph）$G = (V, E)$ 中，边是有序对：$e = (u, v)$，表示从 $u$ 到 $v$ 的有向边。

定义 16.4（多重图） 若允许 $E$ 中存在重复边（平行边），则称 $G$ 为多重图。

定义 16.5（简单图） 简单图是不含自环和平行边的图。

16.1.2 图的基本性质

定义 16.6（顶点的度） 在无向图 $G = (V, E)$ 中，顶点 $v$ 的度定义为：

$$\deg(v) = |{e \in E : v \in e}|$$

定义 16.7（入度与出度） 在有向图 $G = (V, E)$ 中：

入度：$\deg^-(v) = |{(u, v) \in E}|$
出度：$\deg^+(v) = |{(v, u) \in E}|$

定理 16.1（握手定理） 对于无向图 $G = (V, E)$：

$$\sum_{v \in V} \deg(v) = 2|E|$$

证明：每条边 ${u, v}$ 对 $u$ 和 $v$ 的度各贡献 $1$，因此所有顶点度数之和等于边数的 $2$ 倍。 ∎

推论 16.1 任何图中度数为奇数的顶点个数为偶数。

证明：设 $V_{\text{odd}}$ 为度数为奇数的顶点集。由握手定理：

$$\sum_{v \in V} \deg(v) = \sum_{v \in V_{\text{odd}}} \deg(v) + \sum_{v \notin V_{\text{odd}}} \deg(v) = 2|E|$$

右边为偶数，$\sum_{v \notin V_{\text{odd}}} \deg(v)$ 为偶数，故 $\sum_{v \in V_{\text{odd}}} \deg(v)$ 为偶数。奇数之和为偶数当且仅当项数为偶数。 ∎

定理 16.2（有向图的度数关系） 对于有向图 $G = (V, E)$：

$$\sum_{v \in V} \deg^-(v) = \sum_{v \in V} \deg^+(v) = |E|$$

证明：每条有向边 $(u, v)$ 对 $v$ 的入度贡献 $1$，对 $u$ 的出度贡献 $1$。 ∎

16.1.3 路径与连通性

定义 16.8（路径） 图 $G = (V, E)$ 中从 $u$ 到 $v$ 的路径是顶点序列 $P = (v_0, v_1, \ldots, v_k)$，其中：

$v_0 = u$，$v_k = v$
$(v_{i-1}, v_i) \in E$，$\forall i \in {1, \ldots, k}$

定义 16.9（路径长度） 路径 $P = (v_0, v_1, \ldots, v_k)$ 的长度为 $k$（边数）。

定义 16.10（简单路径） 若路径中所有顶点互不相同，则称为简单路径。

定义 16.11（环） 若路径 $P = (v_0, v_1, \ldots, v_k)$ 满足 $v_0 = v_k$ 且 $k \geq 1$，则称 $P$ 为环。

定义 16.12（连通性）

无向图：若存在从 $u$ 到 $v$ 的路径，则称 $u$ 与 $v$ 连通
有向图：若存在从 $u$ 到 $v$ 的有向路径，则称 $u$ 可达 $v$

定义 16.13（连通分量） 无向图 $G$ 的极大连通子图称为连通分量。

定理 16.3 连通关系是等价关系。

证明：

自反性：平凡路径 $(v)$ 表明 $v$ 与 $v$ 连通
对称性：若存在路径 $(v_0, \ldots, v_k)$ 从 $u$ 到 $v$，则 $(v_k, \ldots, v_0)$ 是从 $v$ 到 $u$ 的路径
传递性：若 $u$ 与 $v$ 连通，$v$ 与 $w$ 连通，连接两条路径得 $u$ 与 $w$ 连通

∎

16.1.4 特殊图类

定义 16.14（完全图） $n$ 阶完全图 $K_n$ 是任意两顶点都相邻的简单图。

定理 16.4 $K_n$ 的边数为 $\binom{n}{2} = \frac{n(n-1)}{2}$。

定义 16.15（二部图） 图 $G = (V, E)$ 称为二部图，若存在划分 $V = V_1 \cup V_2$，$V_1 \cap V_2 = \emptyset$，使得所有边连接 $V_1$ 与 $V_2$ 中的顶点。

定理 16.5（二部图判定） 图 $G$ 是二部图当且仅当 $G$ 不含奇环。

证明：（$\Rightarrow$）设 $G$ 是二部图，划分为 $V_1, V_2$。环上的边交替连接 $V_1$ 和 $V_2$，故环长为偶数。

（$\Leftarrow$）设 $G$ 无奇环。对每个连通分量，任选顶点 $s$，定义：

$V_1 = {v : d(s, v) \text{ 为偶数}}$
$V_2 = {v : d(s, v) \text{ 为奇数}}$

若存在边 ${u, v} \subseteq V_1$，则 $d(s, u)$ 和 $d(s, v)$ 均为偶数，存在奇环，矛盾。同理 $V_2$ 内无边。 ∎

定义 16.16（树） 连通无环图称为树。

定理 16.6（树的等价定义） 对于 $n$ 阶图 $G$，以下命题等价：

$G$ 是树
$G$ 连通且有 $n-1$ 条边
$G$ 无环且有 $n-1$ 条边
$G$ 中任意两顶点间存在唯一路径
$G$ 连通，但删除任一边后不连通
$G$ 无环，但添加任一边后产生环

证明：$(1 \Rightarrow 2)$：对 $n$ 归纳。$n=1$ 显然。设 $n > 1$，树有叶子 $v$（度为 $1$ 的顶点）。删去 $v$ 得 $n-1$ 阶树，由归纳假设有 $n-2$ 条边，原树有 $n-1$ 条边。

$(2 \Rightarrow 3)$：若 $G$ 有环，删去环上一边仍连通，边数减少但仍连通，与最小性矛盾。

$(3 \Rightarrow 4)$：连通性显然。若存在两条 $u$-$v$ 路径，则存在环，矛盾。

$(4 \Rightarrow 5)$：连通性显然。删除边 ${u, v}$ 后，原唯一 $u$-$v$ 路径被破坏，故不连通。

$(5 \Rightarrow 6)$：若 $G$ 有环，删除环上一边仍连通，矛盾。添加边 ${u, v}$ 后，原 $u$-$v$ 路径与新边形成环。

$(6 \Rightarrow 1)$：若 $G$ 不连通，添加边连接两分量不产生环，矛盾。 ∎

16.2 图的表示方法

16.2.1 邻接矩阵

定义 16.17（邻接矩阵） 对于 $n$ 阶图 $G = (V, E)$，顶点编号为 ${1, 2, \ldots, n}$，邻接矩阵 $A \in {0, 1}^{n \times n}$ 定义为：

$$A_{ij} = \begin{cases} 1 & \text{若 } (i, j) \in E \ 0 & \text{否则} \end{cases}$$

定理 16.7（邻接矩阵的幂） 设 $A$ 为图的邻接矩阵，则 $A^k_{ij}$ 等于从 $i$ 到 $j$ 长度为 $k$ 的路径条数。

证明：对 $k$ 归纳。$k=1$ 时显然。设对 $k$ 成立，则：

$$A^{k+1}{ij} = \sum^{n} A^k_{il} \cdot A_{lj}$$

$A^k_{il}$ 是 $i$ 到 $l$ 的长度为 $k$ 的路径数，$A_{lj}$ 表示是否有边 $(l, j)$。求和得到 $i$ 到 $j$ 的长度为 $k+1$ 的路径数。 ∎

空间复杂度：$O(|V|^2)$

时间复杂度：

查询边：$O(1)$
遍历邻居：$O(|V|)$
添加/删除边：$O(1)$

16.2.2 邻接表

定义 16.18（邻接表） 对于每个顶点 $v$，存储其邻居列表 $\text{Adj}[v] = {u : (v, u) \in E}$。

空间复杂度：

无向图：$O(|V| + 2|E|) = O(|V| + |E|)$
有向图：$O(|V| + |E|)$

时间复杂度：

查询边：$O(\deg(v))$
遍历邻居：$O(\deg(v))$
添加边：$O(1)$（链表）或 $O(\log \deg(v))$（平衡树）
删除边：$O(\deg(v))$

16.2.3 表示方法比较

操作	邻接矩阵	邻接表
空间	$O(V^2)$	$O(V + E)$
判断边 $(u, v)$	$O(1)$	$O(\deg(u))$
遍历邻居	$O(V)$	$O(\deg(u))$
添加边	$O(1)$	$O(1)$
删除边	$O(1)$	$O(\deg(u))$

定理 16.8 对于稀疏图（$|E| = O(|V|)$），邻接表更优；对于稠密图（$|E| = \Theta(|V|^2)$），邻接矩阵更优。

16.3 图ADT规范

16.3.1 代数规范

ADT Graph[V]
    imports Boolean, Integer, Set, List, V
    
    sorts Graph
    
    operations
        empty           :                              → Graph
        add_vertex      : Graph × V                   → Graph
        add_edge        : Graph × V × V               → Graph
        remove_vertex   : Graph × V                   → Graph
        remove_edge     : Graph × V × V               → Graph
        contains_vertex : Graph × V                   → Boolean
        contains_edge   : Graph × V × V               → Boolean
        vertices        : Graph                       → Set[V]
        edges           : Graph                       → Set[(V, V)]
        neighbors       : Graph × V                   → Set[V]
        degree          : Graph × V                   → Integer
        vertex_count    : Graph                       → Integer
        edge_count      : Graph                       → Integer
    
    axioms
        ∀ g: Graph, v, u, w: V
        
        [V1] contains_vertex(empty, v) = false
        
        [V2] contains_vertex(add_vertex(g, v), v) = true
        
        [V3] v ≠ u ⇒ contains_vertex(add_vertex(g, v), u) = contains_vertex(g, u)
        
        [E1] contains_edge(empty, v, u) = false
        
        [E2] contains_edge(add_edge(g, v, u), v, u) = true
        
        [E3] contains_edge(add_vertex(g, v), u, w) = contains_edge(g, u, w)
        
        [E4] add_edge(g, v, u) = add_edge(add_vertex(add_vertex(g, v), u), v, u)
        
        [N1] neighbors(empty, v) = ∅
        
        [N2] u ≠ w ⇒ neighbors(add_edge(g, v, u), w) = neighbors(g, w)
        
        [N3] neighbors(add_edge(g, v, u), v) = neighbors(g, v) ∪ {u}
        
        [D1] degree(g, v) = |neighbors(g, v)|
        
        [VC1] vertex_count(empty) = 0
        
        [VC2] contains_vertex(g, v) ⇒ vertex_count(add_vertex(g, v)) = vertex_count(g)
        
        [VC3] ¬contains_vertex(g, v) ⇒ vertex_count(add_vertex(g, v)) = vertex_count(g) + 1
        
        [EC1] edge_count(empty) = 0
        
        [EC2] contains_edge(g, v, u) ⇒ edge_count(add_edge(g, v, u)) = edge_count(g)
        
        [EC3] ¬contains_edge(g, v, u) ⇒ edge_count(add_edge(g, v, u)) = edge_count(g) + 1
end ADT

16.4 图的实现

16.4.1 邻接表实现

python

from typing import Dict, List, Set, TypeVar, Generic, Optional, Tuple, Iterator
from collections import defaultdict

V = TypeVar('V')
W = TypeVar('W', int, float)

class Graph(Generic[V]):
    def __init__(self, directed: bool = False):
        self._adjacency: Dict[V, Set[V]] = defaultdict(set)
        self._directed = directed
        self._edge_count = 0
    
    def add_vertex(self, vertex: V) -> None:
        if vertex not in self._adjacency:
            self._adjacency[vertex] = set()
    
    def add_edge(self, u: V, v: V) -> None:
        self.add_vertex(u)
        self.add_vertex(v)
        
        if v not in self._adjacency[u]:
            self._adjacency[u].add(v)
            self._edge_count += 1
        
        if not self._directed and u not in self._adjacency[v]:
            self._adjacency[v].add(u)
    
    def remove_vertex(self, vertex: V) -> None:
        if vertex not in self._adjacency:
            return
        
        for neighbor in list(self._adjacency[vertex]):
            self._adjacency[neighbor].discard(vertex)
            if self._directed:
                self._edge_count -= 1
        
        if not self._directed:
            self._edge_count -= len(self._adjacency[vertex])
        
        del self._adjacency[vertex]
    
    def remove_edge(self, u: V, v: V) -> None:
        if u in self._adjacency and v in self._adjacency[u]:
            self._adjacency[u].discard(v)
            self._edge_count -= 1
        
        if not self._directed and v in self._adjacency and u in self._adjacency[v]:
            self._adjacency[v].discard(u)
    
    def contains_vertex(self, vertex: V) -> bool:
        return vertex in self._adjacency
    
    def contains_edge(self, u: V, v: V) -> bool:
        return u in self._adjacency and v in self._adjacency[u]
    
    def neighbors(self, vertex: V) -> Set[V]:
        return self._adjacency.get(vertex, set()).copy()
    
    def degree(self, vertex: V) -> int:
        return len(self._adjacency.get(vertex, set()))
    
    def in_degree(self, vertex: V) -> int:
        if not self._directed:
            return self.degree(vertex)
        count = 0
        for v in self._adjacency:
            if vertex in self._adjacency[v]:
                count += 1
        return count
    
    def out_degree(self, vertex: V) -> int:
        return self.degree(vertex)
    
    def vertices(self) -> Set[V]:
        return set(self._adjacency.keys())
    
    def edges(self) -> Set[Tuple[V, V]]:
        result = set()
        for u in self._adjacency:
            for v in self._adjacency[u]:
                if self._directed or (v, u) not in result:
                    result.add((u, v))
        return result
    
    def vertex_count(self) -> int:
        return len(self._adjacency)
    
    def edge_count(self) -> int:
        return self._edge_count
    
    def is_directed(self) -> bool:
        return self._directed
    
    def __contains__(self, vertex: V) -> bool:
        return self.contains_vertex(vertex)
    
    def __len__(self) -> int:
        return self.vertex_count()
    
    def __iter__(self) -> Iterator[V]:
        return iter(self._adjacency)
    
    def __repr__(self) -> str:
        edges = [f"({u}, {v})" for u, v in self.edges()]
        return f"Graph(V={self.vertex_count()}, E={self.edge_count()}, edges={edges})"

16.4.2 邻接矩阵实现

python

from typing import Generic, TypeVar, Optional, List, Set, Tuple

V = TypeVar('V')

class AdjacencyMatrixGraph(Generic[V]):
    def __init__(self, vertices: Optional[List[V]] = None, directed: bool = False):
        self._directed = directed
        self._vertex_to_index: Dict[V, int] = {}
        self._index_to_vertex: List[V] = []
        self._matrix: List[List[int]] = []
        self._edge_count = 0
        
        if vertices:
            for v in vertices:
                self._add_vertex_internal(v)
    
    def _add_vertex_internal(self, vertex: V) -> None:
        if vertex in self._vertex_to_index:
            return
        
        idx = len(self._index_to_vertex)
        self._vertex_to_index[vertex] = idx
        self._index_to_vertex.append(vertex)
        
        for row in self._matrix:
            row.append(0)
        self._matrix.append([0] * (idx + 1))
    
    def add_vertex(self, vertex: V) -> None:
        self._add_vertex_internal(vertex)
    
    def add_edge(self, u: V, v: V, weight: int = 1) -> None:
        self._add_vertex_internal(u)
        self._add_vertex_internal(v)
        
        i, j = self._vertex_to_index[u], self._vertex_to_index[v]
        
        if self._matrix[i][j] == 0:
            self._edge_count += 1
        
        self._matrix[i][j] = weight
        
        if not self._directed:
            self._matrix[j][i] = weight
    
    def remove_edge(self, u: V, v: V) -> None:
        if u not in self._vertex_to_index or v not in self._vertex_to_index:
            return
        
        i, j = self._vertex_to_index[u], self._vertex_to_index[v]
        
        if self._matrix[i][j] != 0:
            self._edge_count -= 1
        
        self._matrix[i][j] = 0
        
        if not self._directed:
            self._matrix[j][i] = 0
    
    def contains_vertex(self, vertex: V) -> bool:
        return vertex in self._vertex_to_index
    
    def contains_edge(self, u: V, v: V) -> bool:
        if u not in self._vertex_to_index or v not in self._vertex_to_index:
            return False
        return self._matrix[self._vertex_to_index[u]][self._vertex_to_index[v]] != 0
    
    def get_weight(self, u: V, v: V) -> Optional[int]:
        if not self.contains_edge(u, v):
            return None
        return self._matrix[self._vertex_to_index[u]][self._vertex_to_index[v]]
    
    def neighbors(self, vertex: V) -> Set[V]:
        if vertex not in self._vertex_to_index:
            return set()
        
        i = self._vertex_to_index[vertex]
        return {self._index_to_vertex[j] for j in range(len(self._matrix)) if self._matrix[i][j] != 0}
    
    def degree(self, vertex: V) -> int:
        return len(self.neighbors(vertex))
    
    def vertices(self) -> Set[V]:
        return set(self._index_to_vertex)
    
    def edges(self) -> Set[Tuple[V, V]]:
        result = set()
        n = len(self._matrix)
        for i in range(n):
            for j in range(n):
                if self._matrix[i][j] != 0:
                    u, v = self._index_to_vertex[i], self._index_to_vertex[j]
                    if self._directed or (v, u) not in result:
                        result.add((u, v))
        return result
    
    def vertex_count(self) -> int:
        return len(self._index_to_vertex)
    
    def edge_count(self) -> int:
        return self._edge_count
    
    def get_matrix(self) -> List[List[int]]:
        return [row[:] for row in self._matrix]

16.4.3 带权图实现

python

from typing import Dict, Generic, TypeVar, Optional, Tuple, Set
from dataclasses import dataclass
import math

V = TypeVar('V')
W = TypeVar('W', int, float)

@dataclass
class Edge(Generic[V, W]):
    source: V
    target: V
    weight: W = 1
    
    def __hash__(self):
        return hash((self.source, self.target))
    
    def __eq__(self, other):
        return self.source == other.source and self.target == other.target

class WeightedGraph(Generic[V, W]):
    def __init__(self, directed: bool = False):
        self._adjacency: Dict[V, Dict[V, W]] = {}
        self._directed = directed
        self._edge_count = 0
    
    def add_vertex(self, vertex: V) -> None:
        if vertex not in self._adjacency:
            self._adjacency[vertex] = {}
    
    def add_edge(self, u: V, v: V, weight: W = 1) -> None:
        self.add_vertex(u)
        self.add_vertex(v)
        
        if v not in self._adjacency[u]:
            self._edge_count += 1
        
        self._adjacency[u][v] = weight
        
        if not self._directed:
            self._adjacency[v][u] = weight
    
    def get_weight(self, u: V, v: V) -> Optional[W]:
        if u in self._adjacency and v in self._adjacency[u]:
            return self._adjacency[u][v]
        return None
    
    def set_weight(self, u: V, v: V, weight: W) -> None:
        if u in self._adjacency and v in self._adjacency[u]:
            self._adjacency[u][v] = weight
            if not self._directed:
                self._adjacency[v][u] = weight
    
    def neighbors_with_weights(self, vertex: V) -> Dict[V, W]:
        return self._adjacency.get(vertex, {}).copy()
    
    def edges_with_weights(self) -> Set[Edge[V, W]]:
        result = set()
        for u in self._adjacency:
            for v, w in self._adjacency[u].items():
                if self._directed or Edge(v, u) not in result:
                    result.add(Edge(u, v, w))
        return result
    
    def neighbors(self, vertex: V) -> Set[V]:
        return set(self._adjacency.get(vertex, {}).keys())
    
    def vertices(self) -> Set[V]:
        return set(self._adjacency.keys())
    
    def vertex_count(self) -> int:
        return len(self._adjacency)
    
    def edge_count(self) -> int:
        return self._edge_count

16.5 图的遍历

16.5.1 广度优先搜索（BFS）

算法 16.1（BFS）

BFS(G, s):
    for each vertex u ∈ G.V - {s}:
        u.color = WHITE
        u.d = ∞
        u.π = NIL
    s.color = GRAY
    s.d = 0
    s.π = NIL
    Q = ∅
    ENQUEUE(Q, s)
    while Q ≠ ∅:
        u = DEQUEUE(Q)
        for each v ∈ G.Adj[u]:
            if v.color == WHITE:
                v.color = GRAY
                v.d = u.d + 1
                v.π = u
                ENQUEUE(Q, v)
        u.color = BLACK

定理 16.9（BFS正确性） BFS从源点 $s$ 开始，对每个可达顶点 $v$，$v.d = d(s, v)$（最短距离）。

证明：定义 $d(s, v)$ 为从 $s$ 到 $v$ 的最短路径长度。

引理 1：BFS中，$v.d \geq d(s, v)$。

证明：对入队顺序归纳。$s.d = 0 = d(s, s)$。当 $v$ 被发现时，$v.d = u.d + 1$，其中 $u$ 已出队。由归纳假设 $u.d \geq d(s, u)$，故 $v.d \geq d(s, u) + 1 \geq d(s, v)$。 ∎

引理 2：设队列 $Q = (v_1, v_2, \ldots, v_r)$，则 $v_r.d \leq v_1.d + 1$，且 $v_i.d \leq v_{i+1}.d$。

证明：对操作归纳。初始 $Q = (s)$，$s.d = 0$，成立。出队 $v_1$ 后，可能入队若干 $v$，满足 $v.d = v_1.d + 1$。队列中元素 $d$ 值最多相差 $1$，且非递减。 ∎

主定理证明：设 $v$ 为从 $s$ 可达的顶点，最短路径为 $s = u_0 \to u_1 \to \ldots \to u_k = v$。对 $i$ 归纳证明 $u_i.d = i$。$i=0$ 显然。设 $u_{i-1}.d = i-1$，当 $u_{i-1}$ 出队时发现 $u_i$，故 $u_i.d = i$。因此 $v.d = k = d(s, v)$。 ∎

定理 16.10（BFS时间复杂度） BFS的时间复杂度为 $O(|V| + |E|)$。

证明：每个顶点最多入队一次，出队一次，$O(|V|)$。每条边最多被访问两次（无向图），$O(|E|)$。总复杂度 $O(|V| + |E|)$。 ∎

python

from collections import deque
from typing import Dict, Set, List, TypeVar, Optional, Tuple

V = TypeVar('V')

def bfs(g: Graph[V], source: V) -> Tuple[Dict[V, int], Dict[V, Optional[V]]]:
    distance: Dict[V, int] = {source: 0}
    parent: Dict[V, Optional[V]] = {source: None}
    queue = deque([source])
    
    while queue:
        u = queue.popleft()
        for v in g.neighbors(u):
            if v not in distance:
                distance[v] = distance[u] + 1
                parent[v] = u
                queue.append(v)
    
    return distance, parent

def bfs_path(g: Graph[V], source: V, target: V) -> Optional[List[V]]:
    if source == target:
        return [source]
    
    _, parent = bfs(g, source)
    
    if target not in parent:
        return None
    
    path = []
    current = target
    while current is not None:
        path.append(current)
        current = parent[current]
    
    return path[::-1]

16.5.2 深度优先搜索（DFS）

算法 16.2（DFS）

DFS(G):
    for each vertex u ∈ G.V:
        u.color = WHITE
        u.π = NIL
    time = 0
    for each vertex u ∈ G.V:
        if u.color == WHITE:
            DFS-VISIT(G, u)

DFS-VISIT(G, u):
    time = time + 1
    u.d = time
    u.color = GRAY
    for each v ∈ G.Adj[u]:
        if v.color == WHITE:
            v.π = u
            DFS-VISIT(G, v)
    u.color = BLACK
    time = time + 1
    u.f = time

定义 16.19（时间戳）

发现时间 $v.d$：顶点 $v$ 第一次被发现的时间
完成时间 $v.f$：顶点 $v$ 的所有后代都被探索完成的时间

定理 16.11（括号定理） 在DFS中，对于任意两顶点 $u, v$，以下恰有一个成立：

$[u.d, u.f]$ 与 $[v.d, v.f]$ 完全分离
$[u.d, u.f]$ 完全包含 $[v.d, v.f]$
$[v.d, v.f]$ 完全包含 $[u.d, u.f]$

证明：考察 $u.d$ 与 $v.d$ 的先后。不失一般性，设 $u.d < v.d$。

若 $v$ 在 $u$ 的DFS树中，则 $v.f < u.f$，情况2成立。

若 $v$ 不在 $u$ 的DFS树中，则 $v$ 在 $u$ 完成前未被访问，故 $v.d > u.f$，情况1成立。 ∎

定理 16.12（白色路径定理） $v$ 是 $u$ 的后代当且仅当在发现 $u$ 时，存在从 $u$ 到 $v$ 的白色路径。

证明：（$\Rightarrow$）若 $v$ 是 $u$ 的后代，则存在DFS树路径 $u \to \ldots \to v$，该路径在发现 $u$ 时为白色。

（$\Leftarrow$）设发现 $u$ 时存在白色路径 $u = v_0 \to v_1 \to \ldots \to v_k = v$。对 $k$ 归纳。$k=0$ 显然。设 $v_{k-1}$ 是 $u$ 的后代，则 $v_k$ 在 $v_{k-1}$ 完成前被发现，故 $v_k$ 是 $v_{k-1}$ 的后代，从而是 $u$ 的后代。 ∎

定理 16.13（DFS时间复杂度） DFS的时间复杂度为 $O(|V| + |E|)$。

python

from typing import Dict, List, Set, Optional, Tuple
from enum import Enum, auto

class Color(Enum):
    WHITE = auto()
    GRAY = auto()
    BLACK = auto()

def dfs(g: Graph[V]) -> Tuple[Dict[V, int], Dict[V, int], Dict[V, Optional[V]]]:
    color: Dict[V, Color] = {v: Color.WHITE for v in g.vertices()}
    discovery: Dict[V, int] = {}
    finish: Dict[V, int] = {}
    parent: Dict[V, Optional[V]] = {v: None for v in g.vertices()}
    time = [0]
    
    def dfs_visit(u: V) -> None:
        time[0] += 1
        discovery[u] = time[0]
        color[u] = Color.GRAY
        
        for v in g.neighbors(u):
            if color[v] == Color.WHITE:
                parent[v] = u
                dfs_visit(v)
        
        color[u] = Color.BLACK
        time[0] += 1
        finish[u] = time[0]
    
    for u in g.vertices():
        if color[u] == Color.WHITE:
            dfs_visit(u)
    
    return discovery, finish, parent

def dfs_iterative(g: Graph[V], start: V) -> List[V]:
    visited: Set[V] = set()
    result: List[V] = []
    stack = [start]
    
    while stack:
        u = stack.pop()
        if u in visited:
            continue
        visited.add(u)
        result.append(u)
        
        for v in g.neighbors(u):
            if v not in visited:
                stack.append(v)
    
    return result

16.5.3 边的分类

定义 16.20（边的分类） 在DFS中，边分为四类：

树边：$(u, v)$ 是树边，若 $v$ 通过边 $(u, v)$ 被发现
后向边：$(u, v)$ 是后向边，若 $v$ 是 $u$ 的祖先
前向边：$(u, v)$ 是前向边，若 $v$ 是 $u$ 的后代但非树边
横跨边：其他所有边

定理 16.14（边的判定） 在DFS中，对于边 $(u, v)$：

树边：$v$ 为白色
后向边：$v$ 为灰色
前向边或横跨边：$v$ 为黑色

定理 16.15（无环判定） 无向图通过DFS不含后向边当且仅当图无环。

证明：（$\Rightarrow$）若有后向边 $(u, v)$，则 $v$ 是 $u$ 的祖先，存在从 $v$ 到 $u$ 的树路径，与 $(u, v)$ 形成环。

（$\Leftarrow$）若有环 $C$，设 $v$ 是 $C$ 中第一个被发现的顶点。当DFS探索 $C$ 中其他边时，必有一条边指向 $v$ 或其祖先，形成后向边。 ∎

python

def classify_edges(g: Graph[V]) -> Dict[str, List[Tuple[V, V]]]:
    color: Dict[V, Color] = {v: Color.WHITE for v in g.vertices()}
    discovery: Dict[V, int] = {}
    finish: Dict[V, int] = {}
    time = [0]
    
    tree_edges: List[Tuple[V, V]] = []
    back_edges: List[Tuple[V, V]] = []
    forward_edges: List[Tuple[V, V]] = []
    cross_edges: List[Tuple[V, V]] = []
    
    def dfs_visit(u: V) -> None:
        time[0] += 1
        discovery[u] = time[0]
        color[u] = Color.GRAY
        
        for v in g.neighbors(u):
            if color[v] == Color.WHITE:
                tree_edges.append((u, v))
                dfs_visit(v)
            elif color[v] == Color.GRAY:
                back_edges.append((u, v))
            elif discovery[v] > discovery[u]:
                forward_edges.append((u, v))
            else:
                cross_edges.append((u, v))
        
        color[u] = Color.BLACK
        time[0] += 1
        finish[u] = time[0]
    
    for u in g.vertices():
        if color[u] == Color.WHITE:
            dfs_visit(u)
    
    return {
        'tree': tree_edges,
        'back': back_edges,
        'forward': forward_edges,
        'cross': cross_edges
    }

16.6 连通性分析

16.6.1 连通分量

python

def connected_components(g: Graph[V]) -> List[Set[V]]:
    visited: Set[V] = set()
    components: List[Set[V]] = []
    
    for start in g.vertices():
        if start in visited:
            continue
        
        component: Set[V] = set()
        stack = [start]
        
        while stack:
            u = stack.pop()
            if u in visited:
                continue
            visited.add(u)
            component.add(u)
            
            for v in g.neighbors(u):
                if v not in visited:
                    stack.append(v)
        
        components.append(component)
    
    return components

def is_connected(g: Graph[V]) -> bool:
    if g.vertex_count() == 0:
        return True
    
    components = connected_components(g)
    return len(components) == 1

16.6.2 强连通分量

定义 16.21（强连通分量） 有向图的极大强连通子图称为强连通分量（SCC）。

定理 16.16（Kosaraju定理） 以下算法可在线性时间内找到所有强连通分量：

对图 $G$ 执行DFS，记录完成时间
构造转置图 $G^T$
按完成时间递减顺序对 $G^T$ 执行DFS
每棵DFS树对应一个强连通分量

python

def transpose(g: Graph[V]) -> Graph[V]:
    gt = Graph[V](directed=True)
    for u in g.vertices():
        gt.add_vertex(u)
    for u in g.vertices():
        for v in g.neighbors(u):
            gt.add_edge(v, u)
    return gt

def kosaraju_scc(g: Graph[V]) -> List[Set[V]]:
    discovery, finish, _ = dfs(g)
    
    vertices_by_finish = sorted(g.vertices(), key=lambda v: finish[v], reverse=True)
    
    gt = transpose(g)
    
    visited: Set[V] = set()
    sccs: List[Set[V]] = []
    
    for start in vertices_by_finish:
        if start in visited:
            continue
        
        scc: Set[V] = set()
        stack = [start]
        
        while stack:
            u = stack.pop()
            if u in visited:
                continue
            visited.add(u)
            scc.add(u)
            
            for v in gt.neighbors(u):
                if v not in visited:
                    stack.append(v)
        
        sccs.append(scc)
    
    return sccs

16.6.3 Tarjan算法

定理 16.17（Tarjan算法） Tarjan算法使用一次DFS在线性时间内找到所有强连通分量。

python

def tarjan_scc(g: Graph[V]) -> List[Set[V]]:
    index_counter = [0]
    stack: List[V] = []
    lowlink: Dict[V, int] = {}
    index: Dict[V, int] = {}
    on_stack: Set[V] = set()
    sccs: List[Set[V]] = []
    
    def strongconnect(v: V) -> None:
        index[v] = index_counter[0]
        lowlink[v] = index_counter[0]
        index_counter[0] += 1
        stack.append(v)
        on_stack.add(v)
        
        for w in g.neighbors(v):
            if w not in index:
                strongconnect(w)
                lowlink[v] = min(lowlink[v], lowlink[w])
            elif w in on_stack:
                lowlink[v] = min(lowlink[v], index[w])
        
        if lowlink[v] == index[v]:
            scc: Set[V] = set()
            while True:
                w = stack.pop()
                on_stack.remove(w)
                scc.add(w)
                if w == v:
                    break
            sccs.append(scc)
    
    for v in g.vertices():
        if v not in index:
            strongconnect(v)
    
    return sccs

16.7 本章小结

本章系统介绍了图论基础：

形式化定义：图、路径、连通性的数学定义
基本定理：握手定理、二部图判定、树的等价定义
表示方法：邻接矩阵与邻接表的复杂度分析
遍历算法：BFS与DFS的正确性证明
连通性：连通分量与强连通分量算法

参考文献

Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory. Springer.
Diestel, R. (2017). Graph Theory, 5th ed. Springer.
Cormen, T. H., et al. (2009). Introduction to Algorithms, 3rd ed. MIT Press.
Tarjan, R. E. (1972). Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 146-160.
Kosaraju, S. R. (1978). Strong connectivity algorithm. Unpublished manuscript.

下一章：第17章图遍历与最短路径

第16章 图论基础 ​

学习目标 ​

16.1 图的形式化定义 ​

16.1.1 基本定义 ​

16.1.2 图的基本性质 ​

16.1.3 路径与连通性 ​

16.1.4 特殊图类 ​

16.2 图的表示方法 ​

16.2.1 邻接矩阵 ​

16.2.2 邻接表 ​

16.2.3 表示方法比较 ​

16.3 图ADT规范 ​

16.3.1 代数规范 ​

16.4 图的实现 ​

16.4.1 邻接表实现 ​

16.4.2 邻接矩阵实现 ​

16.4.3 带权图实现 ​

16.5 图的遍历 ​

16.5.1 广度优先搜索（BFS） ​

16.5.2 深度优先搜索（DFS） ​

16.5.3 边的分类 ​

16.6 连通性分析 ​

16.6.1 连通分量 ​

16.6.2 强连通分量 ​

16.6.3 Tarjan算法 ​

16.7 本章小结 ​

参考文献 ​

第16章图论基础

学习目标

16.1 图的形式化定义

16.1.1 基本定义

16.1.2 图的基本性质

16.1.3 路径与连通性

16.1.4 特殊图类

16.2 图的表示方法

16.2.1 邻接矩阵

16.2.2 邻接表

16.2.3 表示方法比较

16.3 图ADT规范

16.3.1 代数规范

16.4 图的实现

16.4.1 邻接表实现

16.4.2 邻接矩阵实现

16.4.3 带权图实现

16.5 图的遍历

16.5.1 广度优先搜索（BFS）

16.5.2 深度优先搜索（DFS）

16.5.3 边的分类

16.6 连通性分析

16.6.1 连通分量

16.6.2 强连通分量

16.6.3 Tarjan算法

16.7 本章小结

参考文献