【数据结构与算法体系】之图算法（一）-基本篇

一、图的基本概念与数学定义

1.1 图的数学定义

图（Graph）是一个二元组 $G = (V, E)$，其中 $V$ 是顶点（Vertex）的有限集合，$E \subseteq V \times V$ 是边（Edge）的集合。设 $|V| = n$，$|E| = m$。

有向图（Directed Graph / Digraph）：边是有序对 $(u, v)$，表示从 $u$ 指向 $v$。例如 Twitter 的关注关系（A 关注 B 不代表 B 关注 A）。

无向图（Undirected Graph）：边是无序对 ${u, v}$，表示 $u$ 与 $v$ 之间的双向连接。例如 Facebook 的好友关系。

带权图（Weighted Graph）：每条边关联一个权重 $w: E \to \mathbb{R}$。例如地图中城市间的距离。

度（Degree）：

无向图中，顶点 $v$ 的度 $\deg(v)$ = 与 $v$ 相连的边数
有向图中，出度 $\deg^+(v)$ = 从 $v$ 出发的边数，入度 $\deg^-(v)$ = 指向 $v$ 的边数

握手引理（Handshaking Lemma）：

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

证明：每条边为其两个端点各贡献 1 度，因此所有顶点的度之和恰好是边数的两倍。推论：任何图中，奇数度顶点的个数必为偶数。

1.2 路径与连通性

路径（Path）：顶点序列 $v_1, v_2, \ldots, v_k$，满足 $\forall i \in [1, k-1]$，$(v_i, v_{i+1}) \in E$（有向图）或 ${v_i, v_{i+1}} \in E$（无向图）。简单路径要求所有顶点互不相同。

连通性：

无向图：若任意两顶点间存在路径，则图是连通的（Connected）
有向图：若任意两顶点间双向都有路径，则图是强连通的（Strongly Connected）；若忽略方向后连通，则称弱连通的（Weakly Connected）

环（Cycle）：起点与终点相同的路径，且至少包含一条边。无向图中要求至少 3 个顶点（避免将单条无向边误判为环）。

二、图的存储方式与内存分析

图有两种基本存储方式，选择哪种取决于图的稠密度和操作需求。

2.1 邻接矩阵（Adjacency Matrix）

使用 $n \times n$ 的二维数组 matrix[i][j]：

// 邻接矩阵
class GraphMatrix {
    int n;
    int[][] matrix; // matrix[i][j] = 1 表示有边, 0 表示无边
    
    public GraphMatrix(int n) {
        this.n = n;
        this.matrix = new int[n][n];
    }
    
    public void addEdge(int u, int v) {
        matrix[u][v] = 1;
        matrix[v][u] = 1; // 无向图
    }
    
    public boolean hasEdge(int u, int v) {
        return matrix[u][v] != 0; // O(1)
    }
}

内存分析：

空间复杂度：$\Theta(n^2)$，无论实际有多少条边
Java int[][] 占用 $4n^2$ 字节（不含对象头）
对于 $n = 10^5$ 的社交网络（例如约有 $10^6$ 条边），矩阵需要 $4 \times 10^{10}$ 字节 ≈ 40 GB，远超现代计算机内存；而邻接表仅需约 $O(n + m) = 10^5 + 10^6$ 条记录

操作复杂度：

查询边 $(u, v)$ 是否存在：$O(1)$
遍历 $v$ 的所有邻居：$O(n)$，即使 $v$ 只有 3 个邻居也必须扫描整行
添加/删除边：$O(1)$

适用场景：稠密图（$m \approx n^2$），如完全图 $K_n$ 有 $n(n-1)/2$ 条边；或需要频繁判断任意两点邻接关系的场景。

2.2 邻接表（Adjacency List）

为每个顶点维护一个列表，存储其所有邻居：

class Graph {
    int V;
    List<Integer>[] adj;  // adj[v] 存储 v 的所有邻居
    
    @SuppressWarnings("unchecked")
    public Graph(int V) {
        this.V = V;
        adj = new List[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }
    
    public void addEdge(int u, int v) {
        adj[u].add(v);
        adj[v].add(u);  // 无向图，两个方向都加
    }
}

内存分析：

空间复杂度：$\Theta(n + m)$（无向图）或 $\Theta(n + m)$（有向图）
每个顶点维护一个 ArrayList：对象头 + 引用数组，动态扩容时额外开销约 1.5x
与邻接矩阵的对比（以 $n = 10^5, m = 10^6$ 为例）：

        邻接矩阵      邻接表
空间     4n² ≈ 40GB   n + 2m ≈ 2×10^6 引用 ≈ 16MB
判断边   O(1)         O(deg(v))
遍历邻居 O(n)         O(deg(v))
添加边   O(1)         O(1) 均摊

操作复杂度：

查询边 $(u, v)$：$O(\deg(u))$，需遍历 $u$ 的邻居列表
遍历 $v$ 的所有邻居：$O(\deg(v))$，恰好访问实际的邻居
添加边：$O(1)$ 均摊（ArrayList 追加）

适用场景：稀疏图（$m \ll n^2$），绝大多数现实世界图都是稀疏的。

2.3 邻接表变体

前向星（Forward Star）：使用连续数组存储所有边，按起点排序，适合静态图（建图后不修改）。空间更紧凑，缓存友好。

链式前向星：竞技编程中常用，完全用数组模拟链表：

int[] head = new int[N]; Arrays.fill(head, -1);
int[] to = new int[M], nxt = new int[M], w = new int[M];
int tot = 0;
void addEdge(int u, int v, int weight) {
    to[tot] = v; w[tot] = weight; nxt[tot] = head[u]; head[u] = tot++;
}

三、广度优先搜索（BFS）

3.1 算法原理

BFS 从起始顶点 $s$ 开始，逐层向外扩展——先访问距离 $s$ 为 1 步的所有顶点，然后是距离 2 步的，以此类推。BFS 使用队列（Queue）辅助实现，保证按距离的升序访问顶点。

算法伪代码：

BFS(G, s):
    for each v in V:
        visited[v] = false; distance[v] = ∞; parent[v] = null
    visited[s] = true; distance[s] = 0; parent[s] = null
    Q = empty queue; Q.enqueue(s)
    while Q is not empty:
        v = Q.dequeue()
        for each neighbor u of v:
            if not visited[u]:
                visited[u] = true
                distance[u] = distance[v] + 1
                parent[u] = v
                Q.enqueue(u)

3.2 完整 Java 实现

import java.util.*;

class BFS {
    static class Result {
        int[] distance;  // distance[v] = 从s到v的最短距离（按边数）
        int[] parent;    // parent[v] = v在BFS树中的父节点
        List<Integer> order; // BFS访问顺序
        
        Result(int n) {
            distance = new int[n];
            parent = new int[n];
            order = new ArrayList<>();
            Arrays.fill(distance, -1);
            Arrays.fill(parent, -1);
        }
    }
    
    public static Result bfs(Graph graph, int start) {
        int n = graph.V;
        Result result = new Result(n);
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        
        visited[start] = true;
        result.distance[start] = 0;
        result.parent[start] = -1;
        queue.offer(start);
        
        while (!queue.isEmpty()) {
            int v = queue.poll();
            result.order.add(v);
            
            for (int u : graph.adj[v]) {
                if (!visited[u]) {
                    visited[u] = true;
                    result.distance[u] = result.distance[v] + 1;
                    result.parent[u] = v;
                    queue.offer(u);
                }
            }
        }
        return result;
    }
    
    // 重构从s到t的最短路径
    public static List<Integer> reconstructPath(int[] parent, int t) {
        List<Integer> path = new ArrayList<>();
        for (int v = t; v != -1; v = parent[v]) {
            path.add(v);
        }
        Collections.reverse(path);
        return path.isEmpty() || path.get(0) != path.get(0) ? path : path;
    }
}

3.3 正确性证明

定理 1（BFS 最短路径）：在无权图 $G$ 中，BFS 计算得到的 distance[v] 等于从 $s$ 到 $v$ 的最短路径上的边数。

证明：设 $\delta(s, v)$ 为从 $s$ 到 $v$ 的最短距离（按边数）。

(1) 首先证明 distance[v] ≥ δ(s, v)。对 BFS 的入队操作进行归纳。$s$ 入队时 distance[s] = 0 = δ(s, s)。假设对某顶点 $v$，当 $v$ 入队时 distance[v] ≥ δ(s, v) 成立。由于 BFS 只根据邻居更新距离，distance[u] = distance[v] + 1 ≥ δ(s, v) + 1。由最短路径的三角不等式，$\delta(s, u) \leq \delta(s, v) + 1$，故 distance[u] ≥ δ(s, u)。

(2) 再证明 distance[v] ≤ δ(s, v)。使用归纳法于 $\delta(s, v)$ 的值。$\delta(s, v) = 0$ 时 $v = s$，成立。假设对所有满足 $\delta(s, u) = k$ 的顶点 $u$ 有 distance[u] = k。任取 $\delta(s, v) = k + 1$ 的顶点 $v$，存在 $u$ 使得 $(u, v) \in E$ 且 $\delta(s, u) = k$。由归纳假设，$u$ 在某个时刻出队且 distance[u] = k。当遍历 $u$ 的邻居时，若 $v$ 尚未被访问，则 distance[v] = k + 1；若 $v$ 已被访问，则 distance[v] ≤ k + 1。综上，distance[v] ≤ k + 1 = δ(s, v)。

由 (1) 和 (2) 得 distance[v] = δ(s, v)。 $\square$

3.4 复杂度分析

时间复杂度：每个顶点恰好入队一次、出队一次，每条边被检查一次（无向图每条边被从两端各检查一次，但 visited 标记确保每个顶点只入队一次）。因此总时间为 $O(V + E)$。

空间复杂度：队列最多容纳 $O(V)$ 个顶点（最坏情况：起始顶点连接所有其他顶点），visited、distance、parent 数组各 $O(V)$。总空间 $O(V)$。

3.5 BFS 树

BFS 过程中形成的 parent 关系构成一棵BFS 树。BFS 树的性质：

包含起点 $s$ 和所有从 $s$ 可达的顶点
对于树中任意顶点 $v$，从 $s$ 到 $v$ 在树中的唯一路径就是图中实际的最短路径
树中任意两个不同层的顶点之间不存在边（否则那个顶点应该在更早的层被访问）

四、深度优先搜索（DFS）

4.1 算法原理与实现

DFS 从起始顶点开始，沿一条路径尽可能深入，直到无法继续后回溯。DFS 天然适合递归实现。

class DFS {
    // 时间戳
    static int time;
    static int[] discover; // 发现时间（进入时）
    static int[] finish;   // 完成时间（退出时）
    static int[] parent;   // DFS树中的父节点
    
    public static void dfs(Graph graph) {
        int n = graph.V;
        boolean[] visited = new boolean[n];
        discover = new int[n];
        finish = new int[n];
        parent = new int[n];
        Arrays.fill(parent, -1);
        time = 0;
        
        for (int v = 0; v < n; v++) {
            if (!visited[v]) {
                dfsVisit(graph, v, visited);
            }
        }
    }
    
    private static void dfsVisit(Graph graph, int v, boolean[] visited) {
        visited[v] = true;
        discover[v] = ++time;  // 记录发现时间
        
        for (int u : graph.adj[v]) {
            if (!visited[u]) {
                parent[u] = v;
                dfsVisit(graph, u, visited);
            }
        }
        
        finish[v] = ++time;  // 记录完成时间
    }
    
    // 迭代版DFS（显式栈）
    public static void dfsIterative(Graph graph, int start, boolean[] visited, 
                                     List<Integer> order) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(start);
        
        while (!stack.isEmpty()) {
            int v = stack.pop();
            if (!visited[v]) {
                visited[v] = true;
                order.add(v);
                // 注意：为了与递归版保持相同的遍历顺序，
                // 需要逆序将邻居入栈
                List<Integer> neighbors = graph.adj[v];
                for (int i = neighbors.size() - 1; i >= 0; i--) {
                    int u = neighbors.get(i);
                    if (!visited[u]) {
                        stack.push(u);
                    }
                }
            }
        }
    }
}

4.2 括号定理（Parenthesis Theorem）

对于 DFS 过程中记录的 discover[v] 和 finish[v]，任意两个顶点 $u$ 和 $v$ 的时间区间满足以下三者之一：

$[discover[u], finish[u]]$ 与 $[discover[v], finish[v]]$ 完全不相交（$u$ 和 $v$ 不在同一棵 DFS 树中，或在不同分支中）
$[discover[u], finish[u]]$ 完全包含 $[discover[v], finish[v]]$（$v$ 是 $u$ 的后代）
$[discover[v], finish[v]]$ 完全包含 $[discover[u], finish[u]]$（$u$ 是 $v$ 的后代）

证明：考虑 DFS 进程中第一次遇到 $u$ 和 $v$ 的情况。设 discover[u] < discover[v]。当时间到达 discover[v] 时，$u$ 是灰色的（正在被探索）。此时有两种可能：(1) $v$ 是 $u$ 的后代，则 finish[v] < finish[u]；(2) $v$ 不是 $u$ 的后代，则 $u$ 在 $v$ 被探索完之前不可能完成，因此 $v$ 的时间区间完全在 $u$ 的区间之后，即 finish[u] < discover[v]。$\square$

4.3 边的分类（Edge Classification）

DFS 过程中，每条边 $(u, v)$ 可被分类为以下四种之一：

    发现时间 d[u] < d[v]?
       /          \
     是            否
     /              \
Tree Edge        d[v] < f[v] < d[u] < f[u]?
(v未访问)           /          \
                 是            否
                 /              \
          Back Edge         Cross Edge
          (v是u的祖先)      (v已完成)

树边（Tree Edge）：$v$ 在 $(u, v)$ 被检查时尚未被访问。$v$ 成为 $u$ 在 DFS 树中的子节点。
后向边（Back Edge）：$v$ 是 $u$ 在 DFS 树中的祖先（$v$ 灰色）。无向图中只有树边和后向边。
前向边（Forward Edge）：$v$ 是 $u$ 的后代但非子节点（$v$ 已完成）。
横叉边（Cross Edge）：$u$ 和 $v$ 不在同一棵 DFS 子树中，$v$ 的时间区间在 $u$ 之前并且不相交。

无向图的性质：无向图的 DFS 中不存在前向边和横叉边。证明：若 $(u, v)$ 是无向边且 d[u] < d[v]，当 DFS 在 $u$ 处检查边 $(u, v)$ 时，若 $v$ 已访问，则 $(u, v)$ 必定是后向边（此时 $v$ 仍在栈中，即 $v$ 是 $u$ 的祖先）；若 $v$ 未访问，则是树边。

4.4 环检测

无向图环检测：DFS 中若遇到一条非父节点的已访问邻居，则存在环。

boolean hasCycleUndirected(Graph graph) {
    boolean[] visited = new boolean[graph.V];
    for (int v = 0; v < graph.V; v++) {
        if (!visited[v]) {
            if (dfsCycleUndirected(graph, v, -1, visited)) return true;
        }
    }
    return false;
}

boolean dfsCycleUndirected(Graph graph, int v, int parent, boolean[] visited) {
    visited[v] = true;
    for (int u : graph.adj[v]) {
        if (!visited[u]) {
            if (dfsCycleUndirected(graph, u, v, visited)) return true;
        } else if (u != parent) {
            // 遇到已访问且非父节点的顶点 → 环
            return true;
        }
    }
    return false;
}

有向图环检测（三色标记法）：

// 0 = WHITE(未访问), 1 = GRAY(在栈中), 2 = BLACK(已完成)
boolean hasCycleDirected(Graph graph) {
    int[] color = new int[graph.V];
    for (int v = 0; v < graph.V; v++) {
        if (color[v] == 0) {
            if (dfsCycleDirected(graph, v, color)) return true;
        }
    }
    return false;
}

boolean dfsCycleDirected(Graph graph, int v, int[] color) {
    color[v] = 1; // GRAY — 正在访问
    for (int u : graph.adj[v]) {
        if (color[u] == 1) return true;   // 后向边 → 环
        if (color[u] == 0) {
            if (dfsCycleDirected(graph, u, color)) return true;
        }
    }
    color[v] = 2; // BLACK — 已完成
    return false;
}

五、拓扑排序（Topological Sort）

5.1 定义与引理

拓扑排序适用于有向无环图（DAG），将 $n$ 个顶点排序为线性序列 $v_1, v_2, \ldots, v_n$，使得对于每条有向边 $(v_i, v_j)$，有 $i < j$。

引理：有向图 $G$ 存在拓扑排序当且仅当 $G$ 是无环的（DAG）。

证明：

($\Rightarrow$) 若 $G$ 有环，设环上顶点为 $v_{i_1} \to v_{i_2} \to \cdots \to v_{i_k} \to v_{i_1}$，则要求 $i_1 < i_2 < \cdots < i_k < i_1$，矛盾。
($\Leftarrow$) 若 $G$ 无环，则 $G$ 至少有一个入度为 0 的顶点（否则从任意顶点出发沿着入边反向行走，必重复访问某顶点，形成环）。取该入度为 0 的顶点作为第一个，删除它及所有出边，递归处理剩余图。

5.2 Kahn 算法（BFS 实现）

List<Integer> topologicalSortKahn(Graph graph) {
    int n = graph.V;
    int[] indegree = new int[n];
    
    // 计算入度
    for (int v = 0; v < n; v++) {
        for (int u : graph.adj[v]) {
            indegree[u]++;
        }
    }
    
    // 入度为0的顶点入队
    Queue<Integer> queue = new LinkedList<>();
    for (int v = 0; v < n; v++) {
        if (indegree[v] == 0) queue.offer(v);
    }
    
    List<Integer> result = new ArrayList<>();
    while (!queue.isEmpty()) {
        int v = queue.poll();
        result.add(v);
        for (int u : graph.adj[v]) {
            if (--indegree[u] == 0) {
                queue.offer(u);
            }
        }
    }
    
    if (result.size() != n) {
        throw new IllegalStateException("图中存在环路，无法拓扑排序");
    }
    return result;
}

复杂度：$O(V + E)$，每个顶点入队一次，每条边被处理一次。

示例演算：考虑课程依赖图：

0 → 1 → 3
↓   ↓   ↑
2 → 4 → 5

入度数组初始化：[0:0, 1:1, 2:1, 3:2, 4:1, 5:1]

第一步：入度为 0 的 {0} 入队，出队 0，1 的入度变为 0，2 的入度变为 0
第二步：{1, 2} 入队 → 出队 1 → 3 入度=1, 4 入度=0 → 4 入队 → 出队 2 → 4 入度=0（已为 0）
第三步：{4} → 3 入度=0, 5 入度=0
第四步：{3, 5} → 依次出队

结果：[0, 1, 2, 4, 3, 5]（可能有多种合法顺序）

5.3 DFS-based 算法

对图进行 DFS，在顶点完成时（递归返回前）将顶点加入结果列表的头部。

算法直觉：DFS 深入到底部（不依赖任何未完成顶点的顶点）后才开始回溯。回溯顺序恰好是依赖关系的逆序——最先完成的是最深层的顶点（不依赖别人），最后完成的是最上层的顶点（被所有人依赖）。

List<Integer> topologicalSortDFS(Graph graph) {
    int n = graph.V;
    boolean[] visited = new boolean[n];
    List<Integer> result = new ArrayList<>(); // 逆序收集
    
    for (int v = 0; v < n; v++) {
        if (!visited[v]) {
            dfsTopo(graph, v, visited, result);
        }
    }
    
    Collections.reverse(result);
    return result;
}

void dfsTopo(Graph graph, int v, boolean[] visited, List<Integer> result) {
    visited[v] = true;
    for (int u : graph.adj[v]) {
        if (!visited[u]) {
            dfsTopo(graph, u, visited, result);
        }
    }
    result.add(v); // 在DFS完成时收集
}

环检测：如果在 DFS 过程中遇到灰色顶点（仍在递归栈中的顶点），则存在环，拓扑排序不可能。

5.4 两种算法对比

特性              Kahn (BFS)           DFS-based
实现基础          入度 + 队列           递归 + 完成时间
环检测           结果长度 != n          三色标记检测后向边
并行性           天然支持并行执行        串行
                      (入度为0的任务可并行)
最小字典序      使用优先队列即可获得    需要额外处理

六、强连通分量（SCC）

在无向图中，”连通分量”就是极大的连通子图。在有向图中，我们关心更强的概念——强连通分量：极大的顶点子集，其中任意两个顶点 $u, v$ 满足 $u \rightsquigarrow v$ 且 $v \rightsquigarrow u$。

缩点图（Condensation Graph）：将每个 SCC 收缩为一个超级顶点后，得到的图必定是 DAG。因为如果缩点图中存在环，则环上的所有 SCC 实际上应合并为一个更大的 SCC。

6.1 Kosaraju 算法（两趟 DFS）

核心洞察：在转置图 $G^T$（将所有边反向的图）中，SCC 保持不变——因为 SCC 定义中的双向可达性在边反转后依然成立。

算法步骤：

第一趟 DFS：在原图 $G$ 上进行 DFS，记录每个顶点的完成时间（后序遍历）
**构建转置图 $G^T$**：将图的所有边方向反转
第二趟 DFS：在 $G^T$ 上按第一趟完成时间的逆序进行 DFS。每棵 DFS 树就是一个 SCC

class Kosaraju {
    public static List<List<Integer>> findSCCs(Graph graph) {
        int n = graph.V;
        
        // 第一趟DFS：记录完成顺序
        boolean[] visited = new boolean[n];
        Deque<Integer> finishOrder = new ArrayDeque<>();
        for (int v = 0; v < n; v++) {
            if (!visited[v]) {
                dfsFirst(graph, v, visited, finishOrder);
            }
        }
        
        // 构建转置图
        Graph reversed = reverseGraph(graph);
        
        // 第二趟DFS：按完成时间逆序
        Arrays.fill(visited, false);
        List<List<Integer>> sccs = new ArrayList<>();
        while (!finishOrder.isEmpty()) {
            int v = finishOrder.pollLast(); // 逆序：从最后完成的开始
            if (!visited[v]) {
                List<Integer> scc = new ArrayList<>();
                dfsSecond(reversed, v, visited, scc);
                sccs.add(scc);
            }
        }
        return sccs;
    }
    
    private static void dfsFirst(Graph g, int v, boolean[] visited, 
                                  Deque<Integer> order) {
        visited[v] = true;
        for (int u : g.adj[v]) {
            if (!visited[u]) dfsFirst(g, u, visited, order);
        }
        order.offerLast(v); // 完成时记录
    }
    
    private static void dfsSecond(Graph g, int v, boolean[] visited, 
                                   List<Integer> scc) {
        visited[v] = true;
        scc.add(v);
        for (int u : g.adj[v]) {
            if (!visited[u]) dfsSecond(g, u, visited, scc);
        }
    }
    
    private static Graph reverseGraph(Graph g) {
        Graph rev = new Graph(g.V);
        for (int v = 0; v < g.V; v++) {
            for (int u : g.adj[v]) {
                rev.adj[u].add(v); // 反转边方向
            }
        }
        return rev;
    }
}

正确性直觉：在转置图中，如果我们从缩点图（DAG）的一个”汇”（出度为 0 的 SCC）开始 DFS，那么 DFS 不会离开这个 SCC。而原图中完成时间最晚的顶点恰好属于转置图中入度为 0 的 SCC（即原图中出度为 0 的 SCC 在转置图中变为入度为 0，在转置图 DFS 中自然成为一个”源”）。因此按逆完成顺序在转置图上 DFS 正好将 SCC 逐个隔离出来。

复杂度：两趟 DFS，$O(V + E)$ 时间，$O(V + E)$ 空间（存储转置图）。

6.2 Tarjan 算法（一趟 DFS）

Tarjan 算法只需一趟 DFS，通过维护 dfn（深度优先编号 / 发现时间）和 low（能追溯到的最早祖先编号）数组在线识别 SCC。

核心定义：

dfn[v]：顶点 $v$ 在 DFS 中的发现时间戳
low[v]：从 $v$ 出发，通过至多一条后向边能到达的顶点的最小 dfn 值

SCC 判定条件：当 dfn[v] == low[v] 时，$v$ 是其所在 SCC 的”根”，当前 DFS 栈中 $v$ 及其之上的所有顶点构成一个 SCC。

class Tarjan {
    static int time;
    static int[] dfn, low;
    static boolean[] inStack;
    static Deque<Integer> stack;
    static List<List<Integer>> sccs;
    
    public static List<List<Integer>> findSCCs(Graph graph) {
        int n = graph.V;
        dfn = new int[n];
        low = new int[n];
        inStack = new boolean[n];
        stack = new ArrayDeque<>();
        sccs = new ArrayList<>();
        time = 0;
        Arrays.fill(dfn, -1);
        
        for (int v = 0; v < n; v++) {
            if (dfn[v] == -1) {
                tarjan(graph, v);
            }
        }
        return sccs;
    }
    
    private static void tarjan(Graph graph, int v) {
        dfn[v] = low[v] = ++time;
        stack.push(v);
        inStack[v] = true;
        
        for (int u : graph.adj[v]) {
            if (dfn[u] == -1) {
                // 树边
                tarjan(graph, u);
                low[v] = Math.min(low[v], low[u]);
            } else if (inStack[u]) {
                // 后向边 / 横叉边到仍在栈中的顶点
                low[v] = Math.min(low[v], dfn[u]);
            }
            // 横叉边到已完成SCC的顶点：忽略
        }
        
        // SCC根节点判定
        if (low[v] == dfn[v]) {
            List<Integer> scc = new ArrayList<>();
            int u;
            do {
                u = stack.pop();
                inStack[u] = false;
                scc.add(u);
            } while (u != v);
            sccs.add(scc);
        }
    }
}

复杂度：一趟 DFS，$O(V + E)$ 时间，$O(V)$ 额外空间（不含递归栈）。对比 Kosaraju，Tarjan 不需要构建转置图，常数因子更小。

七、二分图检测（Bipartite Graph Checking）

定义：图 $G = (V, E)$ 是二分图，若存在划分 $V = L \cup R$（$L \cap R = \emptyset$），使得每条边的两个端点分别属于 $L$ 和 $R$。

定理：图是二分图当且仅当它不包含奇数长度的环。

证明：

($\Rightarrow$) 若 $G$ 是二分图且有环 $v_1, v_2, \ldots, v_k, v_1$。设 $v_1 \in L$，则 $v_2 \in R$, $v_3 \in L$, …, 即奇数下标在 $L$，偶数下标在 $R$。由于边 $(v_k, v_1)$ 连接两个集合，须有 $v_k \in R$（若 $v_1 \in L$），所以 $k$ 为偶数。因此不存在奇数环。
($\Leftarrow$) 若图中无奇数环，可以通过 BFS 染色构造二分划分。 $\square$

完整实现

class Bipartite {
    // 返回染色方案，若不可二分返回null
    public static int[] checkBipartite(Graph graph) {
        int n = graph.V;
        int[] color = new int[n]; // 0:未染色, 1:红, -1:蓝
        
        for (int v = 0; v < n; v++) {
            if (color[v] == 0) {
                if (!bfsColor(graph, v, color)) {
                    return null; // 不可二分
                }
            }
        }
        return color;
    }
    
    private static boolean bfsColor(Graph graph, int start, int[] color) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        color[start] = 1; // 染红色
        
        while (!queue.isEmpty()) {
            int v = queue.poll();
            for (int u : graph.adj[v]) {
                if (color[u] == 0) {
                    color[u] = -color[v]; // 染相反颜色
                    queue.offer(u);
                } else if (color[u] == color[v]) {
                    return false; // 相邻顶点同色 → 奇数环
                }
            }
        }
        return true;
    }
}

应用：二分图是匈牙利算法求最大匹配的基础。典型场景：将工作分配给工人（一边是工人，一边是工作）；将学生分配到项目组；电影推荐中用户-电影构成天然二分图。

八、BFS vs DFS 系统对比

┌──────────────────┬─────────────────────┬─────────────────────┐
│      特性         │        BFS           │        DFS           │
├──────────────────┼─────────────────────┼─────────────────────┤
│ 数据结构          │ 队列 (FIFO)          │ 栈 (递归/显式)       │
│ 遍历方式          │ 按层（宽度优先）      │ 深入优先             │
│ 最短路径(无权)    │ ✅ 保证最短          │ ❌ 不保证            │
│ 内存(宽图)        │ 可能很大(整层顶点)    │ O(树深度)            │
│ 内存(深图)        │ 好                    │ 递归栈可能溢出       │
│ 环检测            │ ✓ (间接)             │ ✓ (直接, 后向边)     │
│ 连通分量          │ ✓                    │ ✓                    │
│ 拓扑排序          │ ✓ (Kahn)             │ ✓ (DFS-based)        │
│ 二分图检测        │ ✓                    │ ✓                    │
│ 回溯类问题        │ 不适合                │ ✅ 天然适合           │
│ 迷宫最短路径      │ ✅                    │ ❌                    │
│ 时间复杂度        │ O(V+E)               │ O(V+E)               │
│ 空间复杂度        │ O(V)                 │ O(V) (递归栈)        │
└──────────────────┴─────────────────────┴─────────────────────┘

九、面试常见追问（精选 5 题）

问题一：DFS 的递归和迭代实现的遍历顺序是否相同？为什么？

回答：不一定相同。递归版 DFS 在遍历邻居列表时，对于每个未访问邻居立即递归深入，完成后才处理下一个邻居。迭代版使用显式栈时，若简单地将所有未访问邻居顺序入栈，则实际访问顺序与递归相反（因为栈的 LIFO 特性——先入栈的后被访问，而递归版先遇到先深入）。

为保持一致，应在入栈时逆序将邻居入栈（即 for i = size-1 downto 0 将邻居 push）。但要注意：这也只保证访问顺序一致；discover/finish 时间戳的精确模拟需要额外的状态管理（需要在栈中同时保存”进入”和”退出”事件）。

问题二：如何找到无向图的所有桥（Bridges）和割点（Articulation Points）？

回答：DFS 的 low 值（类似 Tarjan 算法）可以高效地找到桥和割点：

桥：无向边 $(u, v)$（$u$ 是 $v$ 的父节点）是桥当且仅当 low[v] > dfn[u]。含义：从 $v$ 及其后代出发，即使使用后向边也无法到达 $u$ 或 $u$ 的祖先。
割点：顶点 $u$ 是割点当且仅当：(1) $u$ 是 DFS 树的根且有至少两个子节点，或 (2) $u$ 不是根，存在子节点 $v$ 使得 low[v] ≥ dfn[u]。

复杂度 $O(V + E)$，一趟 DFS。

// 查找无向图所有桥
void findBridges(Graph g, int v, int parent) {
    visited[v] = true;
    dfn[v] = low[v] = ++time;
    for (int u : g.adj[v]) {
        if (u == parent) continue;
        if (!visited[u]) {
            findBridges(g, u, v);
            low[v] = Math.min(low[v], low[u]);
            if (low[u] > dfn[v]) {
                System.out.println("桥: " + v + " - " + u);
            }
        } else {
            low[v] = Math.min(low[v], dfn[u]);
        }
    }
}

问题三：给定一个有向图，如何判断它是否是半连通的（Semiconnected）？

回答：有向图是半连通的，如果对任意两个顶点 $u, v$，至少存在一条从 $u$ 到 $v$ 或从 $v$ 到 $u$ 的路径。判断方法：

使用 Kosaraju/Tarjan 求出所有 SCC，构建缩点图 $G’$（DAG）
对 $G’$ 进行拓扑排序，得到序列 $s_1, s_2, \ldots, s_k$
检查：对于每个 $i \in [1, k-1]$，是否存在边 $(s_i, s_{i+1})$。若全部满足，则因拓扑序中每个 SCC 都能到达下一个 SCC（通过传递性），从而整个序列串成了一条路径，保证半连通性。

复杂度 $O(V + E)$。

问题四：为什么无向图 DFS 只有树边和后向边，没有前向边和横叉边？

回答：考虑无向边 $(u, v)$ 在 DFS 中的遭遇时刻，假设 discover[u] < discover[v]。

当我们在 $u$ 处检查这条边时，$v$ 尚未被访问（因为 discover[u] < discover[v]）。但我们检查 $(u, v)$ 的那一刻，$v$ 必然尚未被访问——因为如果 $v$ 已经被访问了，那么由于图是无向的，从 $v$ 出发的 DFS 必然会检查边 $(v, u)$，而那时 $u$ 还未被访问（discover[u] < discover[v]），所以 $u$ 会成为 $v$ 的子节点。但这就意味着 discover[v] < discover[u]，矛盾。

因此，在无向图 DFS 中，检查 $(u, v)$ 时 $v$ 只有两种状态：(1) 未访问 → 树边；(2) 已访问 → $v$ 必定是 $u$ 的祖先（后向边）。前向边和横叉边不可能出现。

问题五：BFS 能用来求有权图的最短路径吗？为什么 Dijkstra 可以被视为”广义 BFS”？

回答：BFS 不能直接用于有权图，因为 BFS 假设每条边的”代价”相同（等价于权值均为 1）。但有一个启发性视角：Dijkstra 算法是 BFS 在有权图上的推广。

可以将权值为 $w$ 的边视为由 $w$ 条虚拟的单位权边串连而成（插入 $w-1$ 个虚拟顶点）。那么原有权图上的 Dijkstra 等价于在这个扩展的无权图上运行 BFS。但在实际实现中，我们不会真的展开这些虚拟边（$w = 10^9$ 时会爆炸）。Dijkstra 用优先队列”跳过”虚拟顶点：当顶点 $v$ 的距离确定为 $d$ 时，其邻居 $u$ 的距离候选值为 $d + w(v, u)$，优先队列选择当前距离最小的顶点出队，等价于 BFS 中那 $w$ 个虚拟顶点被逐个跳过。

这个视角也解释了为什么 Dijkstra 要求非负权——如果存在负权边，虚拟拓展边的 BFS 模型就不成立（BFS 的前提是”距离随层数单调递增”）。

十、总结

本文涵盖了图数据结构与算法的基础知识体系：

存储结构：邻接矩阵（$O(n^2)$ 空间，适合稠密图）与邻接表（$O(n+m)$ 空间，适合稀疏图）
BFS：逐层遍历，无权图最短路径，$O(V+E)$
DFS：深入优先，边分类（树边/后向边/前向边/横叉边），环检测（三色标记法）
拓扑排序：Kahn 算法（BFS + 入度）与 DFS-based 算法，仅适用于 DAG
SCC：Kosaraju（两趟 DFS + 转置图）与 Tarjan（一趟 DFS + lowlink），$O(V+E)$
二分图检测：BFS 交替染色，当且仅当无奇数环

这些基础算法是后续高级图算法（最小生成树、最短路径、网络流）的必要前提。熟练掌握它们的时间/空间复杂度、正确性证明以及各自适用的场景，不仅对于技术面试至关重要，更是设计高效图数据系统的基石。

推荐阅读本系列的下一篇文章：【数据结构与算法体系】之图算法（二）-最小生成树, 了解 Prim、Kruskal 和 Boruvka 算法如何在加权连通图中找到最小代价的生成树。