4.1 Undirected Graphs：表示、DFS、BFS与连通分量

4.1 · Undirected Graphs覆盖 6 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

能解释“4.1 · Undirected Graphs”如何从邻接表表示出发，用 DFS、BFS、连通分量与符号图回答无向图查询
能逐项核对无向图、图数据类型与表示、深度优先搜索、广度优先搜索、连通分量、符号图，并区分作者站内容与本页独立补充
能按“邻接表空间 Θ(V+E)；DFS/BFS 单次搜索时间 Θ(V+E)”手算一个最小输入，逐步检查“marked 只表示已发现顶点；edgeTo 链必须回到源点，BFS 首次发现给出最少边路径”
能注入“递归 DFS 在标记前访问邻居造成环上重复递归，或 BFS 出队时才标记导致重复入队”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“4·1 · Undirected Graphs”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“4·1 · Undirected Graphs”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“4·1 · Undirected Graphs”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：4.1 · Undirected Graphs

1. 无向图：在本页通过“建立双向邻接”连接解释、交互状态和练习验收。
2. 图数据类型与表示：在本页通过“发现并标记顶点”连接解释、交互状态和练习验收。
3. 深度优先搜索：在本页通过“记录来源边”连接解释、交互状态和练习验收。
4. 广度优先搜索：在本页通过“展开前沿”连接解释、交互状态和练习验收。
5. 连通分量：在本页通过“重建路径或分量”连接解释、交互状态和练习验收。
6. 符号图：在本页通过“建立双向邻接”连接解释、交互状态和练习验收。

从“关系不是一条线”开始

Sequence、tree都给元素一个受限结构；无向图（undirected graphs）允许任意pairs建立对称relation。社交连接、双向道路、网络links、分子bonds与maze passages都可建模为vertices V和edges E。

先预测从source 0做DFS得到的path是否一定与BFS一样短。不会。DFS只在first encounter时记录parent，neighbor iteration order可让它先绕一条长路；BFS按distance layers发现vertices，因此first encounter已经是fewest-edge path。

官方4.1从graph data type and representation出发，用DFS解决reachability与path，再用BFS解决unweighted shortest paths，以重复DFS标注connected components，最后用SymbolGraph把real-world string names适配到dense integer Graph core。

selected vertex = 2 · degree = 3

adj(2)

0 3 4

Undirected edge v-w同时出现在adj(v)与adj(w)；isolated vertex仍属于V，但adjacency list为空。

4.1.1 Graph model：vertices、edges与paths

Graph G=(V,E) 中，edge v-w 是unordered pair。Self-loop连接vertex自身；parallel edges让同一pair出现多次。Official Graph允许两者，并约定self-loop在adj(v)出现两次、degree贡献2。

Vertex degree是incident edges数量。每条普通edge对两个endpoints各贡献1，self-loop也贡献2，因此handshaking lemma：

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

Average degree随之为：

\overline d=\frac{2E}{V}

Path是由相邻vertices组成的sequence；simple path不重复vertex。Cycle首尾相同且至少含一条edge；simple cycle除首尾外不重复。Connected表示两vertices之间存在path，这是一种equivalence relation，会把V划分成disjoint connected components。

Graph semantics不包含layout：画面上两edges交叉不意味着交点是vertex。Vertex identity与edge list才是source of truth，visual position只帮助理解。

4.1.2 Graph data type and representation：adjacency lists

图数据类型与表示（graph data type and representation）的minimal API是：V()、E()、addEdge(v,w)、adj(v)与degree。Official implementation使用vertex-indexed Bag<Integer>[] adj：

public class Graph {
    private final int V;
    private int E;
    private Bag<Integer>[] adj;
 
    public void addEdge(int v, int w) {
        validateVertex(v);
        validateVertex(w);
        E++;
        adj[v].add(w);
        adj[w].add(v);
    }
 
    public Iterable<Integer> adj(int v) {
        validateVertex(v);
        return adj[v];
    }
}

Undirected edge必须写入两张lists；E只加一次。若漏一侧，traversal reachability会依起点方向而变化，已经不再是undirected graph。Input vertices必须落在0到V减1，constructor对negative counts与truncated input也应拒绝。

Adjacency-list space是Theta(V+E)，因为有V个bags与2E个edge endpoints。AddEdge constant time，遍历adj(v) proportional to degree(v)。Adjacency matrix占Theta(V squared)；它适合dense graph或constant-time edge-existence query，但对本书常见sparse graph浪费大量empty cells。

所有adjacency lists总迭代量是：

\sum_v |\mathrm{adj}(v)|=2E

这正是DFS/BFS linear graph time中E只出现一次量级的原因。若client频繁问hasEdge(v,w)，list implementation需scan smaller degree或额外index，API requirement会影响representation choice。

4.1.3 Depth-first search：沿一条branch走到底

深度优先搜索（depth-first search）只有两条核心规则：

进入vertex立即mark。
对每个unmarked neighbor递归visit。

private void dfs(Graph G, int v) {
    marked[v] = true;
    for (int w : G.adj(v))
        if (!marked[w]) dfs(G, w);
}

Mark必须发生在递归neighbors之前。若在return时才mark，一个cycle中的vertices会互相重复递归，甚至stack overflow。每个reachable vertex只enter一次，每个incident edge endpoint只inspect一次，所以从source访问其component的time proportional to vertices加edges in that component；whole graph worst caseTheta(V+E)。

令source可达子图含 (V_s) 个vertices与 (E_s) 条edges，则单源DFS的精确规模界为：

T_{\mathrm{DFS}}=\Theta(V_s+E_s)

Recursive call stack worst proportional topath length；line graph可达到V。Iterative DFS可用explicit stack避免language call-stack limit，但为了复现recursive neighbor order，需要控制push顺序。换顺序会改变DFS tree与path，却不改变reachable set。

4.1.4 Finding paths：edgeTo是DFS tree parent array

当DFS由v首次发现w时设置 edgeTo[w]=v。这些parent edges形成root在source s的DFS tree。hasPathTo(v)就是marked[v]；pathTo(v)沿edgeTo从v反向回s，再用stack反转：

private void dfs(Graph G, int v) {
    marked[v] = true;
    for (int w : G.adj(v)) {
        if (!marked[w]) {
            edgeTo[w] = v;
            dfs(G, w);
        }
    }
}

路径证书包含：首vertex是s、末vertex是v、每个consecutive pair确实在G中相邻、无parent cycle。若unmarked则path应为null/empty，不可返回只含target的伪路径。

DFS保证finding some path。它不维护distance，也不比较alternative parents；neighbor iteration order决定first discovery。Path output time proportional topath length，preprocessing仍Theta(V+E)。

4.1.5 Breadth-first search：FIFO构造distance layers

广度优先搜索（breadth-first search）维护marked但把待展开vertices放入queue：

private void bfs(Graph G, int s) {
    Queue<Integer> queue = new Queue<Integer>();
    marked[s] = true;
    distTo[s] = 0;
    queue.enqueue(s);
 
    while (!queue.isEmpty()) {
        int v = queue.dequeue();
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                edgeTo[w] = v;
                distTo[w] = distTo[v] + 1;
                marked[w] = true;
                queue.enqueue(w);
            }
        }
    }
}

Mark要在enqueue时发生，而非dequeue时；否则多个frontier parents可把同一vertex重复入队，edgeTo反复覆盖、queue膨胀。FIFO invariant保证queue中distance不倒退：所有distance d vertices在任何distance d+1 vertex展开前处理。

Shortest-path proof按distance induction。Source distance 0正确；当从distance d的v首次发现w，已知不存在更短未处理path，否则w应在更早layer被发现，因此 distTo[w]=d+1 minimal。

BFS与DFS都访问每个reachable vertex/edge constant times，whole graph worst Theta(V+E)，extra arrays/queue Theta(V)。区别不是Big-O，而是state invariant与result guarantee：DFS path arbitrary，BFS path minimizesnumber of edges。Weighted graph不能用普通BFS比较total weight，下一节weighted algorithms会另行处理。

4.1.6 Connected components：一次预处理，constant-time query

连通分量（connected components）可用outer loop加DFS：

for (int v = 0; v < G.V(); v++) {
    if (!marked[v]) {
        dfs(G, v);
        count++;
    }
}
 
private void dfs(Graph G, int v) {
    marked[v] = true;
    id[v] = count;
    size[count]++;
    for (int w : G.adj(v))
        if (!marked[w]) dfs(G, w);
}

每次outer loop遇到unmarked vertex，就发现一个尚未标号的component，并给整块vertices相同id。PreprocessingTheta(V+E)，之后 connected(v,w)只比较 id[v]==id[w]，constant time；size(v)读取其component size。

Partition certificate要求每个vertex恰有一个id，ids contiguous from 0 to count minus1，同id任意pair reachable，different ids之间不存在edge。最后一条可快速检查：遍历每条edge，两个endpoints ids必须相同。

Section 1.5的union-find适合edges逐渐到达的dynamic connectivity；CC适合static graph一次遍历后大量queries。两者回答类似问题，但input/update model不同。

4.1.7 More DFS applications：共享traversal，替换extra state

DFS skeleton还能解决cycle detection、bipartite two-color、bridge/articulation与flood fill。关键不是复制一段递归，而是增加problem-specific state：

shared traversal

DFS marked[]

extra state

parent + edgeTo

result certificate

return to marked non-parent vertex

DFS skeleton不变，problem-specific state决定cycle、two-color、bridge与implicit-region semantics。

Undirected cycle detection记录parent，遇到marked non-parent neighbor即有cycle；self-loop/parallel-edge需单独正确处理。
Bipartite在tree edge给neighbor opposite color；发现same-color edge时产生odd-cycle certificate。
Bridge维护preorder与low-link；child subtree无法通过back edge到ancestor时，parent edge是cut edge。
Flood fill不必显式构建Graph，按grid bounds和color生成implicit neighbors。

这些applications仍以Theta(V+E)为目标，但result certificate不同。只断言boolean不够，cycle应返回edge sequence，non-bipartite应返回odd cycle，bridge应验证移除后component count增加。

4.1.8 Symbol graphs：names在边界，integers在核心

符号图（symbol graphs）解决real data使用airport、movie、performer等strings，而Graph algorithms要求0到V减1dense indices的问题。

Official SymbolGraph构建三部分：

First pass：ST将每个new name映射到next integer。
Inverse array keys[index]=name。
Second pass：把每行names转indices，再向Graph加edges。

ST<String, Integer> st = new ST<String, Integer>();
String[] keys = new String[st.size()];
for (String name : st.keys()) keys[st.get(name)] = name;
 
Graph graph = new Graph(st.size());
int v = st.get(fields[0]);
for (int i = 1; i < fields.length; i++)
    graph.addEdge(v, st.get(fields[i]));

Name-index round trip必须满足 nameOf(indexOf(name))==name。Delimiter、trim、case与Unicode normalization在both passes保持一致，否则second pass可能查不到first pass建立的vertex。Dense ids让core arrays compact，也让DFS/BFS无需知道domain strings。

DegreesOfSeparation用SymbolGraph做mapping、BFS做shortest path，再把indices映射回names。若source/target不在ST应显式报告unknown；若在图中但different component，则distance infinity，不应混为同一种“not found”。

统一验收：从representation到path certificate

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“4.1 · Undirected Graphs”的两个最小情境间切换，再逐项选择正式概念。预测“邻接表空间 Θ(V+E)；DFS/BFS 单次搜索时间 Θ(V+E)”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

4.1 · Undirected Graphs：对象、操作与不变量

从邻接表表示出发，用 DFS、BFS、连通分量与符号图回答无向图查询

选择最小情境

切换正式概念

路径对照: 在含环图中从 0 到 5 同时运行 DFS 与 BFS
当前观察: undirected graphs：两者都证明可达，只有 BFS 保证边数最少

邻接表空间 Θ(V+E)；DFS/BFS 单次搜索时间 Θ(V+E)

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

无向图：在实验 1 中指出对应状态，并写出一个通过条件。
图数据类型与表示：在实验 2 中指出对应状态，并写出一个通过条件。
深度优先搜索：在实验 3 中指出对应状态，并写出一个通过条件。
广度优先搜索：在实验 1 中指出对应状态，并写出一个通过条件。
连通分量：在实验 2 中指出对应状态，并写出一个通过条件。
符号图：在实验 3 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“邻接表空间 Θ(V+E)；DFS/BFS 单次搜索时间 Θ(V+E)”不是孤立结论？

问题 3：故障恢复。 怎样证明“递归 DFS 在标记前访问邻居造成环上重复递归，或 BFS 出队时才标记导致重复入队”已经修复？

保存V/E、邻接表、marked、edgeTo、队列/栈轨迹、component id 与路径预言机作为正常基线；注入该故障并标记第一个违反“marked 只表示已发现顶点；edgeTo 链必须回到源点，BFS 首次发现给出最少边路径”的状态；撤销后用完全相同的输入、版本和随机种子重放。只有全部状态与独立预言机重新一致，才可发布修复结论。

本章回顾

Undirected edge是unordered endpoint pair，在两侧adjacency lists各出现一次。
Degree sum为2E；adjacency-list space与whole traversal work都是Theta(V+E)。
DFS在enter时mark并递归unmarked neighbors，edgeTo形成source-rooted DFS tree。
DFS能给some path但不保证shortest，neighbor order可改变tree。
BFS以FIFO按distance layers展开，在enqueue时mark，得到fewest-edge paths与distTo。
CC对每个unmarked vertex启动DFS，linear preprocessing后connected query constant。
Cycle、bipartite、bridge和flood fill复用DFS skeleton，但需要不同extra state/certificates。
SymbolGraph用ST、inverse array与integer Graph隔离domain names和algorithm core。