Mika Field Notes

Article

算法导论-CH20-基本图算法

算法导论-CH20-图的基本概念和数据结构，待补充摘要。

May 9, 2026 修考 36 min read

CS61B 课程笔记：图与图的遍历 (Graphs and Traversals)

本笔记结合了 CS61B Lecture 22 (Graphs 1) 与 Lecture 23 (Graphs 2) 的课堂内容及个人手写笔记，对树遍历、图的定义、图的表示方法、深度优先搜索（DFS）及广度优先搜索（BFS）进行了系统性的整理与修正。

一、 树与树的遍历 (Tree Traversals)

1. 树的定义 (Tree Definition)

树（Tree）是图的一种特例。一个结构要被称为树，必须满足以下两个条件：

  1. 拥有一组节点（Nodes/Vertices）与一组连接这些节点的边（Edges）。
  2. 约束条件：任意两个节点之间有且仅有一条路径（即不存在环，且全连通）。

📌 注意：并非所有的家族谱系都是树，如果存在近亲结婚等情况导致产生环路，它在图论上就不是一棵树。

2. 树的遍历分类与直观理解

遍历（Traversal）本质上是按照某种特定的顺序“访问”树中的所有节点。与线性表（List）不同，树的非线性结构决定了它有多种遍历顺序，每种顺序都有其独特的应用场景。

(1) 层序遍历 (Level Order Traversal)

  • 顺序：从上到下，从左到右（类似于英文的阅读顺序）。
  • 直观感受：探索每个层级的所有元素，再进入下一层。

(2) 深度优先遍历 (Depth-First Traversals, DFS)

深度优先有三种经典方式：前序（Preorder）、中序（Inorder）*和*后序（Postorder）。

遍历方式递归定义形象比喻 / 直观体悟典型应用场景
前序 (Preorder)先访问当前节点，再递归遍历其子节点。即：Node -> Left -> Right像书本大纲打印：先展示第 1 章标题（父节点），再深入展示第 1.1 节、1.2 节（子节点）。打印目录树（Directory Listing）、复制树结构。
中序 (Inorder)先递归遍历左子树，再访问当前节点，最后递归右子树。即：Left -> Node -> Right重力投影法：感觉可以将所有节点垂直投影到地面上。从左到右读出投影后的字母，即为中序遍历结果。二叉搜索树（BST）的中序遍历能够输出一个升序序列。
后序 (Postorder)先递归遍历子节点，最后访问当前节点。即：Left -> Right -> Node计算文件夹大小：想要知道一个父文件夹的大小，必须先计算其所有子文件夹的大小并进行累加，最后加上父文件夹自身的大小。统计文件系统大小、自底向上的表达式求值。

3. 树遍历的形象化技巧与例题

🌟 中序遍历的投影法 (Visual Trick)

如下图所示，我们将二叉搜索树的所有节点垂直向下做投影：

       D
     /   \
    B     F
   / \   / \
  A   C E   G
================= (地面)
  A B C D E F G  <-- 投影结果（天然有序）
  • 投影结果：A -> B -> C -> D -> E -> F -> G

🌟 绕圈标记法 (The Perimeter Trick)

如果我们沿着树的外围画一条逆时针的环绕曲线：

image-20260522151509908

  • 前序遍历：每次经过节点的左侧时进行访问（Visit）。
  • 中序遍历：每次经过节点的底部时进行访问（Visit）。
  • 后序遍历：每次经过节点的右侧时进行访问（Visit）。

📂 课例：后序遍历计算文件夹大小

在计算文件夹大小时，必须采用自底向上的后序遍历。其递归伪代码实现如下：

public int postOrderSize(BSTNode x) {
    if (x == null) {
        return 0;
    }
    int total = 0;
    // 1. 先计算所有子文件夹的大小（递归 Left & Right）
    for (BSTNode c : x.children()) {
        total += postOrderSize(c);
    }
    // 2. 最后加上当前文件夹自身的文件大小（访问 Node）
    total += x.fileSize();
    return total;
}

二、 图的基本概念与表示法 (Graph & Representations)

1. 图的定义 (Graph Definition)

图（Graph）由以下两部分组成：

  • 一组顶点（Vertices / Nodes，记作 VV）。
  • 一组边（Edges，记作 EE），每条边连接两个顶点。

在 CS61B 中，除非特别声明，我们默认讨论的都是简单图（Simple Graph）：

  • 无自环（No Loops）：没有边将一个顶点连接到它自身。
  • 无平行边（No Parallel Edges）：任意两个顶点之间最多只有一条边相连。

树与图的关系

“所有的树都是图，但不是所有的图都是树。” 树是一个**无环（Acyclic）且连通（Connected）**的无向图。

2. 图的分类方式

  1. 有向图 (Directed Graph) vs 无向图 (Undirected Graph)：边是否有方向。
  2. 有环图 (Cyclic Graph) vs 无环图 (Acyclic Graph)：图中是否存在至少一个环路。
  3. 带权图 (Weighted Graph)：边或节点上带有标签（如距离、花费等权重）。

3. 图的表示方法 (Graph Representations)

为了在计算机中存储和操作图，通常有以下三种具体的表示方法。假设图中有 VV 个顶点，EE 条边。

(1) 邻接矩阵 (Adjacency Matrix)

  • 原理：使用一个大小为 V×VV \times V 的二维布尔数组 adj[i][j]。如果顶点 i 与 j 之间存在边，则 adj[i][j] = true（或 1），否则为 false（或 0）。
  • 直观感受：两节点之间有联系就是 1，没有就是 0。
  • 特点：对于无向图，该矩阵关于主对角线对称。
  • 空间复杂度：Θ(V2)\Theta(V^2)。

(2) 边集 (Edge Sets)

  • 原理：用一个集合（如 HashSet<Edge>）来存储所有的边，每一条边可以用一个二元组 (u, v) 表示。
  • 空间复杂度：Θ(E)\Theta(E)。

(3) 邻接表 (Adjacency List) —— 最常用

  • 原理：维护一个大小为 VV 的数组（或列表），数组的每个索引 v 处存储一个列表，该列表包含所有与顶点 v 相邻的顶点。
  • 直观感受：使用列表的数组来实现。
  • 特点：对于稀疏图（Sparse Graph，E≪V2E \ll V^2）非常高效，是实际应用中最常见的图表示法。
  • 空间复杂度：Θ(V+E)\Theta(V + E)。

4. 课例：不同表示法下的图打印时间复杂度分析

题目：实现一个 print(Graph G) 函数，打印出图中所有的边。其结构如下：

public static void print(Graph G) {
    for (int v = 0; v < G.V(); v += 1) {
        for (int w : G.adj(v)) {
            System.out.println(v + "-" + w);
        }
    }
}

❓ 思考 1：如果图使用“邻接表”表示，时间复杂度是多少？

  • 分析：
    • 外层循环 v 执行 VV 次。
    • 内层循环通过迭代器访问 G.adj(v)。在邻接表中，所有顶点的邻接链表长度之和为 2E2E（对于无向图，每条边被存储两次）。
    • 因此，内层循环的总迭代次数为 Θ(E)\Theta(E)。
  • 结论：时间复杂度为 Θ(V+E)\Theta(V + E)。

❓ 思考 2：如果图使用“邻接矩阵”表示，时间复杂度是多少？

  • 分析：
    • 虽然我们调用的是 G.adj(v)，但因为底层是邻接矩阵，为了找出某个顶点 v 的所有邻居，迭代器在底层必须扫描整个长度为 VV 的矩阵行。
    • 因此，每一次调用 G.adj(v) 的迭代过程都需要 Θ(V)\Theta(V) 的时间。
    • 外部循环执行 VV 次，每次都需要扫描长度为 VV 的行。
  • 结论：时间复杂度退化为 Θ(V2)\Theta(V^2)。

三、 深度优先搜索 (Depth First Search, DFS)

1. 动因：s-t 连通性问题 (s-t Connectivity)

  • 问题：给定源点 ss 和目标点 tt，判断它们之间是否存在一条路径（即 ss 和 tt 是否连通）。

  • 朴素递归尝试：

    判断 s == t？如果是，返回 true。
否则，对于 s 的每一个邻居 v：
    如果 connected(v, t) 返回 true，则返回 true。
返回 false。

  • 致命缺陷（容易陷入 Loop）： 如果图中存在环（例如 0−10 - 1 相连），在查询 connected(0, 7) 时，由于没有记录哪些节点已经被访问过，程序会在 connected(0, 7) -> connected(1, 7) -> connected(0, 7) 之间无限循环导致栈溢出。

2. DFS 核心思想与 SOP (标准作业流程)

为了解决环路导致的无限循环问题，我们需要在访问节点时进行标记（Mark）。

💡 DFS 本质

探索某个邻居的整个子图，直到不能再深入为止，然后才回溯去探索下一个邻居。

📋 DFS 递归 SOP

  1. 标记当前节点 ss 为已访问（marked[s] = true）。
  2. 判断当前节点 ss 是否为目标节点 tt。如果是，返回 true。
  3. 对于当前节点 ss 的每一个未被标记（Unmarked）的邻居 vv：
    • 递归调用 DFS 探索 vv。
  4. 如果所有邻居都探索完毕仍未找到通路，返回 false。

3. DFS 代码实现 (DepthFirstPaths)

以下是基于普林斯顿 Graph API 的经典 DFS 路径查找类实现。它不仅能判断连通性，还能记录具体的路径（通过 edgeTo 数组）。


    /** DFS 核心递归流程 —— 这个代码必须要熟练掌握 */
    private void dfs(Graph G, int v) {
        marked[v] = true; // 1. 标记当前节点
        for (int w : G.adj(v)) { // 2. 遍历邻居
            if (!marked[w]) { // 3. 只访问未标记的邻居
                edgeTo[w] = v; // 4. 记录 w 是由 v 走过来的
                dfs(G, w);     // 5. 递归调用
            }
        }
    }

    /** 判断起点 s 是否有一条路径通往顶点 v */
    public boolean hasPathTo(int v) {
        return marked[v];
    }

    /** 返回从起点 s 到顶点 v 的完整路径，若不连通则返回 null */
    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)) {
            return null;
        }
        List<Integer> path = new ArrayList<>();
        // 从终点 v 沿着 edgeTo 往回倒推，直到起点 s
        for (int x = v; x != s; x = edgeTo[x]) {
            path.add(x);
        }
        path.add(s);
        Collections.reverse(path); // 反转列表，使其从 s 开始到 v 结束
        return path;
    }
}

4. DFS 时间与空间复杂度分析

(1) 时间复杂度（基于邻接表表示）：O(V+E)O(V + E)

  • 为什么顶点走一次？ 因为有 marked 数组的保护，每个顶点 vv 只会触发一次 dfs(G, v) 调用。故顶点访问总开销为 O(V)O(V)。
  • 为什么边会走两次？ 在无向图中，对于每条边 (u, v)：
    • 当我们在顶点 u 时，会检查 v 是否被标记。
    • 当我们在顶点 v 时，会检查 u 是否被标记。
    • 也就是说，每条边都会被检查恰好 2 次（有向图中检查 1 次）。因此，边检查的总开销为 O(E)O(E)。
  • 为什么不能简写为 O(E)O(E)？ 即使图中一条边都没有（E=0E = 0），构造函数中初始化大小为 VV 的 marked 和 edgeTo 数组也需要耗费 Θ(V)\Theta(V) 的时间。

(2) 空间复杂度：Θ(V)\Theta(V)

  • 需要创建长度为 VV 的 marked 数组和 edgeTo 数组，以及最坏情况下深度为 VV 的递归调用栈。

四、 广度优先搜索 (Breadth First Search, BFS)

1. 动因：s-t 最短路径问题

DFS 能够帮我们找到一条从 ss 到 tt 的路径，但这条路径不一定是最短的（DFS 喜欢一头扎到黑）。如果我们希望找到步数最少（边数最少）的路径，就需要使用广度优先搜索（BFS）。

💡 BFS 本质

BFS 类似于树的层序遍历。它按照距离起点的远近（即边数），呈“波纹状”向外层层扫荡。

2. BFS 核心工具：队列 (Queue)

由于 BFS 需要先访问完“当前距离的所有节点”，再访问“更远距离的节点”，我们无法使用递归（递归本质上是利用系统栈，具有先进后出的 DFS 特性）。 我们必须借助一个队列（Queue）作为工作集（常称为 Fringe / 边缘集 ），利用其先进先出 (FIFO) 的特性。

3. BFS 标准作业流程 (SOP) —— 必须掌握

  1. 初始化一个队列 fringe，将起点 s 放入队列，并将 s 标记为已访问（marked[s] = true）。
  2. 当队列 fringe 不为空时，重复以下步骤：
    • (1) 从队列头部移出（Dequeue）一个顶点 v。
    • (2) 对于 v 的每一个未被标记（Unmarked）的邻居 n：
      • 标记 n：marked[n] = true。
      • 记录路径：edgeTo[n] = v。
      • 记录距离：distTo[n] = distTo[v] + 1。
      • 入队：将 n 添加到队列尾部（Enqueue）。

4. BFS 模拟执行过程 (Dry Run)

假设有图如下，起点为 0：

   1 --- 2 --- 5
 /             | \
0              |  6 --- 7
 \             | /
   4 --------- 8
步骤移出顶点 vv正在检查的邻居 nn队列 fringe 的状态关键更新信息
初始--[0]marked[0]=T, distTo[0]=0
101, 4[1, 4]marked[1,4]=T, edgeTo[1,4]=0, distTo=1
212（0已标记）[4, 2]marked[2]=T, edgeTo[2]=1, distTo[2]=2
348（1已标记）[2, 8]marked[8]=T, edgeTo[8]=4, distTo[8]=2
425（1已标记）[8, 5]marked[5]=T, edgeTo[5]=2, distTo[5]=3
586（5,4已标记）[5, 6]marked[6]=T, edgeTo[6]=8, distTo[6]=3
65无未标记邻居[6]-
767[7]marked[7]=T, edgeTo[7]=6, distTo[7]=4
87无未标记邻居[]队列空，运行结束。

5. BFS 代码实现 (BreadthFirstPaths)

import java.util.LinkedList;
import java.util.Queue;

public class BreadthFirstPaths {
    private boolean[] marked;
    private int[] edgeTo;
    private int[] distTo; // 记录从起点 s 到每个顶点的最短边数
    private final int s;

    public BreadthFirstPaths(Graph G, int s) {
        this.s = s;
        this.marked = new boolean[G.V()];
        this.edgeTo = new int[G.V()];
        this.distTo = new int[G.V()];
        // 初始化距离数组为最大值，表示初始不可达
        for (int v = 0; v < G.V(); v++) {
            distTo[v] = Integer.MAX_VALUE;
        }
        bfs(G, s);
    }

    /** BFS 核心迭代实现 —— 必须会手写 */
    private void bfs(Graph G, int s) {
        Queue<Integer> fringe = new LinkedList<>();
        
        // 1. 起点初始化
        fringe.add(s);
        marked[s] = true;
        distTo[s] = 0;

        while (!fringe.isEmpty()) {
            // 2. 移出队列头节点
            int v = fringe.poll(); 
            
            // 3. 遍历未标记邻居
            for (int w : G.adj(v)) {
                if (!marked[w]) {
                    fringe.add(w);      // 放入队列尾部
                    marked[w] = true;   // 立即标记为已访问（防止重复入队）
                    edgeTo[w] = v;      // 记录路径
                    distTo[w] = distTo[v] + 1; // 累加距离
                }
            }
        }
    }

    public boolean hasPathTo(int v) {
        return marked[v];
    }

    public int distTo(int v) {
        return distTo[v];
    }
}

五、 对比与总结 (Summary)

1. DFS 与 BFS 核心性质对比表格

性质 / 算法深度优先搜索 (DFS)广度优先搜索 (BFS)
核心数据结构系统递归栈（Stack）显式队列（Queue）
探索策略孤军深入，一往无前齐头并进，层层扫荡
经典应用连通性检测（s-t）、环路检测、拓扑排序最短路径（无权图）、最小生成树基础
时间复杂度 (邻接表)Θ(V+E)\Theta(V + E)Θ(V+E)\Theta(V + E)
时间复杂度 (邻接矩阵)Θ(V2)\Theta(V^2)Θ(V2)\Theta(V^2)
空间复杂度Θ(V)\Theta(V)Θ(V)\Theta(V)

2. 核心考点与闭坑指南

  1. 防环机制：在图的遍历中，不论是 DFS 还是 BFS，必须在入队或递归前将节点标记为 marked = true。否则一旦图中有环，必然陷入死循环。
  2. 入队即标记（BFS 关键）：在 BFS 中，节点被检测到未标记后，应该立刻设为 marked[w] = true 并入队。如果等出队时才标记，会导致同一个节点被多次重复加入队列，造成无意义的空间浪费和时间增加。
  3. 图表示法决定性能上限：
    • 邻接表上做 DFS/BFS 是高效的 O(V+E)O(V+E)；
    • 邻接矩阵上由于遍历每个节点的邻居都强制需要 O(V)O(V)，因此算法整体复杂度会退化为 O(V2)O(V^2)。

五、 有向无环图（DAG）与拓扑排序（Topological Sort）

1. 有向无环图 (Directed Acyclic Graph, DAG)

有向无环图（DAG）是一个有方向且不存在任何环的图。DAG 在现实中被广泛用来建模“依赖关系”或者有“先后次序”的流程，例如排课计划、工程项目的工序逻辑等。

2. 拓扑排序的直观理解

💡 拓扑排序的本质

拓扑排序（Topological Sort）：在图中找到一个节点的线性序列，使得图中任意一条有向边 u→vu \to v，uu 在序列中都出现在 vv 之前。也就是说，这个序列满足了任务先后发生的逻辑顺序。

🌟 排序的图形直观

如果你在纸上将拓扑排序好的节点排成一横列，你会发现图中所有的有向边（箭头）都是从左边指向右边的，绝无向左逆流的箭头（如下图所示）。

[ C ] ------> [ F ] ------> [ G ]
  \                         /
   `--------> [ A ] ------>`

⚠️ 约束前提：拓扑排序有且仅在有向无环图（DAG）中才能实现。 如果图中有环，必然存在某种互为因果的死循环（如 A→B→C→AA \to B \to C \to A），此时不可能排出一个合理的先后发生顺序。

3. 拓扑排序算法：逆后序法 (Reverse Postorder)

手写笔记中提到：Topological ordering is given by the reverse of postorder list.（拓扑序是由 DFS 逆后序列表给出的）。

📋 拓扑排序 SOP

  1. 初始化一个空列表 postorder 记录 DFS 的后序返回顺序，以及一个布尔数组 marked。
  2. 依次遍历图中的所有顶点，如果顶点 v 未被标记，则调用 DFS(v)。
    • DFS(v) 流程：
      • (1) 标记 v 为已访问（marked[v] = true）。
      • (2) 递归访问 v 的所有未标记邻居。
      • (3) 当 v 的所有邻居都递归完毕、准备从递归函数返回时，将 v 加入 postorder 列表的尾部。
  3. 整个图的顶点都遍历完成后，将整个 postorder 列表进行反转（Reverse）。
  4. 反转后的结果即为一个合法的拓扑排序。

4. 课例：8 顶点拓扑排序轨迹模拟 (Trace)

在课件中，有如下 DAG。我们通过 DFS 来寻找它的逆后序。

   C ---> F ---> G
   |      |
   v      v
   A ---> D
   |      |
   v      v
   B ---> E ---> H

假设我们首先从 入度（indegree）为 0 的顶点 A 出发调用 DFS：

🔄 模拟调用回溯链

  1. 调用 dfs(A)，标记 marked[A] = true
  2. 访问邻居 B →\to 调用 dfs(B)，标记 marked[B] = true
  3. 访问邻居 E →\to 调用 dfs(E)，标记 marked[E] = true
  4. 访问邻居 H →\to 调用 dfs(H)，标记 marked[H] = true
    • H 没有出边。dfs(H) 准备返回 →\to 记录后序：postorder = [H]
  5. 回溯到 E，E 的邻居都访问完了，dfs(E) 返回 →\to 记录后序：postorder = [H, E]
  6. 回溯到 B，B 的邻居都访问完了，dfs(B) 返回 →\to 记录后序：postorder = [H, E, B]
  7. 回溯到 A，发现 A 还有另一个未标记邻居 D →\to 调用 dfs(D)，标记 marked[D] = true
  8. D 的唯一邻居 E 已被标记。dfs(D) 准备返回 →\to 记录后序：postorder = [H, E, B, D]
  9. 回溯并结束 dfs(A) →\to 记录后序：postorder = [H, E, B, D, A]

由于图中有未标记节点，接下来我们从 C 出发调用 dfs(C)： 10. 调用 dfs(C)，标记 marked[C] = true 11. 访问邻居 F →\to 调用 dfs(F)，标记 marked[F] = true 12. 访问邻居 G →\to 调用 dfs(G)，标记 marked[G] = true * G 没有未标记出边。dfs(G) 返回 →\to 记录后序：postorder = [H, E, B, D, A, G] 13. 回溯并结束 dfs(F) →\to 记录后序：postorder = [H, E, B, D, A, G, F] 14. 回溯并结束 dfs(C) →\to 记录后序：postorder = [H, E, B, D, A, G, F, C]

🏁 结果整理

  • 最终后序 (Postorder)：[H, E, B, D, A, G, F, C]
  • 逆后序即拓扑排序 (Reverse Postorder)：[C, F, G, A, D, B, E, H]

5. 拓扑排序代码实现 (Topological)

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Topological {
    private boolean[] marked;
    private List<Integer> postorder; // 存储后序遍历结果

    public Topological(Graph G) {
        this.marked = new boolean[G.V()];
        this.postorder = new ArrayList<>();
        
        // 遍历所有节点，确保非连通图也能完全拓扑排序 (有重启的 DFS)
        for (int v = 0; v < G.V(); v++) {
            if (!marked[v]) {
                dfs(G, v);
            }
        }
    }

    private void dfs(Graph G, int v) {
        marked[v] = true;
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                dfs(G, w);
            }
        }
        postorder.add(v); // 后序：子节点全部递归完毕后，再加入列表
    }

    /** 返回拓扑排序结果 */
    public Iterable<Integer> order() {
        List<Integer> reversePost = new ArrayList<>(postorder);
        Collections.reverse(reversePost); // 反转后序得到拓扑序
        return reversePost;
    }
}
  • 时间复杂度：Θ(V+E)\Theta(V + E) (每个顶点访问一次，每条边扫描一遍)。
  • 空间复杂度：Θ(V)\Theta(V)。

六、 DAG 上的最短路径与最长路径算法（DAG SPT & LPT）

1. Dijkstra 算法在负权边下的局限性

在存在负权边（Negative Edges）的图中，经典的 Dijkstra 算法会失效。

  • 失效原因：Dijkstra 算法基于贪心策略。一个节点一旦被移出优先队列（Visited），它的最短路径值就被固定，之后不会被重新松弛（Relax）。但如果后续路径中存在大幅度的负权边，之前固定下的距离可能并不是真正最小的。

2. DAG 最短路径算法 (DAG SPT)：按拓扑序松弛

在 DAG（有向无环图）中，不论是否存在负权边，我们都可以利用拓扑序，在 Θ(V+E)\Theta(V + E) 极其高效的时间内求出单源最短路径。

💡 核心机制

按照拓扑排序的顺序依次遍历顶点，每次遍历到一个顶点时，对它所有的出边进行松弛（Relax）操作。因为拓扑排序保证了在处理顶点 vv 时，所有能到达 vv 的前期顶点都已经被处理完毕，因此 distTo[v]distTo[v] 此时已经是绝对正确的最短路径值，绝不会再发生变动！

📋 DAG SPT 代码实现

public class AcyclicSP {
    private double[] distTo;
    private DirectedEdge[] edgeTo;

    public AcyclicSP(EdgeWeightedDigraph G, int s) {
        distTo = new double[G.V()];
        edgeTo = new DirectedEdge[G.V()];

        for (int v = 0; v < G.V(); v++) {
            distTo[v] = Double.POSITIVE_INFINITY;
        }
        distTo[s] = 0.0;

        // 1. 获取 DAG 的拓扑排序
        Topological top = new Topological(G);
        
        // 2. 按照拓扑序依次松弛每个顶点的出边
        for (int v : top.order()) {
            relax(G, v);
        }
    }

    private void relax(EdgeWeightedDigraph G, int v) {
        for (DirectedEdge e : G.adj(v)) {
            int w = e.to();
            if (distTo[w] > distTo[v] + e.weight()) {
                distTo[w] = distTo[v] + e.weight();
                edgeTo[w] = e;
            }
        }
    }
}

3. DAG 最长路径算法 (DAG LPT)

❓ 最长路径问题的痛点

在普通图中求单源最长简单路径是一个极度困难的 NP-Hard 问题（目前最好的已知算法也是指数级别的，即 O(2V)O(2^V)）。 然而，在 DAG 中，我们可以使用极其聪明的数学性质在 Θ(V+E)\Theta(V + E) 内解决最长路径。

🌟 核心公式与规约思想

由于：

−(−a+−b+−c)=a+b+c-(-a + -b + -c) = a + b + c

我们可以将 DAG LPT 完美规约（Reduce）到 DAG SPT 上：

  1. 边权取反：创建原图 GG 的一个副本 G′G'，将其中所有边的权重乘以 −1-1。
  2. 求解最短路径：在 G′G' 上运行 DAG SPT 算法。
  3. 距离还原：将得到的 distTo 数组的值再次乘以 −1-1，即可得到原图的最长路径大小（此时的 edgeTo 指向完全不需要修改，就是正确的路径）。

七、 规约（Reductions）

1. 规约的定义 (Reduction Definition)

规约（Reduction）是理论计算机科学中最为核心的工具之一。

💡 浅显比喻

“爬山” 规约到 “坐缆车”：如果我们能通过坐缆车来到达山顶，那么爬山这个问题就迎刃而解了（即：缆车服务是解决爬山问题的一个更强/等价的子程序）。

📋 学术定义

如果解决任务 QQ 的子程序可以直接用来解决任务 PP，我们就说：问题 PP 可以规约到问题 QQ（PP reduces to QQ）。

在刚才的例子中，“DAG 最长路径问题 (DAG-LPT)” 成功规约到了 “DAG 最短路径问题 (DAG-SPT)”。

2. 经典 A-level 规约例题：3SAT 规约到独立集问题 (3SAT Reduces to Independent Set)

规约不仅存在于图论问题之间，甚至能将逻辑问题与图论问题进行跨界转换。

(1) 问题背景

  • 3SAT 问题：给定一个布尔逻辑表达式 Φ\Phi（如 (x1∨x2∨¬x3)∧(¬x1∨x2∨x4)…(x_1 \lor x_2 \lor \neg x_3) \land (\neg x_1 \lor x_2 \lor x_4) \dots），寻找一组逻辑变量的真值指派（True/False），使得整个表达式为真。
  • 独立集问题 (Independent Set)：在图中寻找一个包含 kk 个顶点的集合，使得这 kk 个顶点两两之间都没有边相连。

(2) 规约构造 SOP (如何把 3SAT 转换成图)

给定 3SAT 实例 Φ\Phi，构造独立集图 GG：

  1. 子句变三角形：对于 Φ\Phi 中的每一个三变量子句（如 (x1∨x2∨x3)(x_1 \lor x_2 \lor x_3)），在图 GG 中建立 33 个对应的顶点，并将它们两两相连组成一个三角形。这意味着在独立集中，每个三角形（子句）里最多只能选出 11 个顶点。
  2. 矛盾相连：将图中所有互为相反数的文字节点相连（例如将所有的 x1x_1 节点与 ¬x1\neg x_1 节点连一条边）。这保证了我们不能同时将 x1x_1 和 ¬x1\neg x_1 都选入独立集。
  3. 设定目标值 kk：k=k = 子句的总数量。

🏁 规约结论

如果在构造出来的图 GG 中能够找到一个大小为 kk 的独立集，那么这个独立集选中的顶点就对应了 3SAT 的一组可行解（这些被选中的变量全设为 True，即可使整个 3SAT 表达式被满足）。

八、 总结 (Summary)

1. 核心性质对比大图谱

算法 / 问题适用图类型核心思想 / 机制时间复杂度空间复杂度解决痛点
DFS Paths任意图递归栈，标记防止无限 LoopO(V+E)O(V + E)Θ(V)\Theta(V)s-t 连通性路径查找
BFS Paths任意无权图显式队列 (Fringe) 层层扫荡O(V+E)O(V + E)Θ(V)\Theta(V)无权图中的最短路径
拓扑排序DAGDFS 逆后序 (Reverse Postorder)Θ(V+E)\Theta(V + E)Θ(V)\Theta(V)任务先后依赖性排序
DAG SPTDAG (可含负边)按照拓扑序依次松弛出边Θ(V+E)\Theta(V + E)Θ(V)\Theta(V)在含负权边的图中求最短路
DAG LPTDAG取反边权 →\to 运行 DAG SPT →\to 还原Θ(V+E)\Theta(V + E)Θ(V)\Theta(V)高效求解最长路径

2. 核心考点与闭坑指南

  1. 拓扑排序判定：考试中如果让你写拓扑排序，第一步要检查图是否为 DAG。只要图里包含环，拓扑排序就彻底不存在。
  2. 后序（Postorder）与逆后序（Reverse Postorder）：不要混淆。DFS 遍历完邻居后把当前节点放进 list 尾部是后序。将后序反转（Reverse）才是拓扑排序。
  3. 规约性质的方向性：如果 PP 规约到 QQ，说明 QQ 至少和 PP 一样难。若 QQ 有高效算法，则 PP 也有高效算法；反之，若 PP 被证明极其难解，那么 QQ 也一定极其难解。