第 8 章 图

Graph

引入

假设一个网络中有多台路由器和交换机，链路把它们连接起来，并带有延迟或代价。

只看这一张网络拓扑，我们就可能提出完全不同的问题：

• 两台设备之间是否连通？
• 怎样系统地访问所有设备而不遗漏？
• 一个数据包从 A 到 B 的最低代价路径是什么？
• 如果某些依赖关系有方向，怎样确定合法执行顺序？

这些问题面对的是同一批顶点和边，却需要完全不同的算法。

当“对象之间的连接关系”本身成为问题核心时，我们应该怎样表示关系，又怎样在关系网络上计算？

应用案例

同一种“顶点 + 边”抽象还支撑着很多真实系统：

• 万维网（World Wide Web，Web）：页面通过超链接形成巨大的有向图
• 构建系统：目标与依赖关系形成有向无环图（Directed Acyclic Graph，DAG），决定构建顺序
• 检索增强生成（Retrieval-Augmented Generation，RAG）与 GraphRAG：文档、实体、文本块之间可以显式构成图，再做邻域遍历或基于路径的检索
• 智能体工作流：任务、工具、子任务之间的依赖关系常被建模成有向无环图，用拓扑序（topological order）判断哪些步骤已经可以执行

同一个图上可以提出连通性、遍历、生成树（spanning tree）、最短路径（shortest path）、拓扑排序（topological sorting）等不同计算问题。

本章将把重点放在这种“问题类型 → 表示方式 → 算法选择”的对应关系上。

学习目标

• 掌握图的定义、术语和基本分类
• 掌握邻接矩阵（adjacency matrix）、邻接表（adjacency list）、逆邻接表（reverse adjacency list）、十字链表（orthogonal list）和邻接多重表（adjacency multilist）
• 掌握深度优先搜索（Depth-First Search，DFS）、广度优先搜索（Breadth-First Search，BFS）、连通分量（connected component）和生成树
• 掌握 Kruskal 与 Prim 最小生成树（minimum spanning tree）算法
• 掌握 Dijkstra、Bellman-Ford、Floyd 最短路径算法
• 掌握拓扑排序和顶点活动网（Activity-on-Vertex，AOV）
• 理解边活动网（Activity-on-Edge，AOE）、关键路径（critical path）、最早/最迟开始时间

本章路线图

图
Graph

图的语言
顶点 · 边 · 方向 · 权重 · 连通 存储表示
邻接矩阵 · 邻接表 · 链式结构 遍历
深度优先 / 广度优先 · 连通分量 最小生成树
Kruskal / Prim · 连接所有点 最短路径
Dijkstra · Bellman-Ford · Floyd 有向无环图
拓扑排序 · 依赖关系 关键路径
边活动网 · 项目工期瓶颈

图的语言

图的定义

图定义为：

\[ G=(V,E) \]

其中：

• \(V\) 是非空有限顶点（vertex）集合
• \(E\) 是边（edge）集合

无向图（undirected graph）的边是无序对：

\[ (u,v)=(v,u) \]

有向图（directed graph）的边是有序对：

\[ \langle u,v\rangle \ne \langle v,u\rangle \]

无向图与有向图

这里默认不讨论多重图。

完全图（complete graph）

• 无向完全图：任意两个不同顶点之间都有一条边，\(|E|=\frac{n(n-1)}{2}\)。
• 有向完全图：任意两个不同顶点之间两个方向的边都存在，\(|E|=n(n-1)\)。

完全图代表最密集的简单图（simple graph）。

顶点的度（degree）

无向图中，顶点 \(v\) 的度 \(TD(v)\) 是与 \(v\) 关联的边数；有向图还要区分：

• 入度（in-degree）\(ID(v)\)：指向 \(v\) 的边数
• 出度（out-degree）\(OD(v)\)：从 \(v\) 出发的边数

因此 \(TD(v)=ID(v)+OD(v)\)。

无向图满足 \(2|E|=\sum_{v\in V}TD(v)\)。

路径（path）、简单路径和环

路径是顶点序列 \(v_1,v_2,\ldots,v_k\)。在无向图中，每对相邻顶点之间必须有边；在有向图中，还必须沿着边的方向，从 \(v_i\) 走到 \(v_{i+1}\)。

• 简单路径（simple path）：顶点不重复。
• 简单环（simple cycle）：起点和终点相同，除此之外顶点不重复。

连通性

• 无向图中，任意两个顶点之间都有路径，则图连通；连通分量是极大连通子图。
• 有向图中，任意两个不同顶点 \(u,v\) 都能互相到达，则图强连通（strongly connected）。
• 强连通分量（strongly connected component, SCC）是极大强连通子图。

网络

边带权的图称为带权图（weighted graph），教材中也常称为网络（network）。权值可以表示距离、时间、成本、容量或风险；图是否连通是另一个独立性质，并不是“网络”这个称呼的前提。

最小生成树和最短路径都建立在带权图上。

存储表示

邻接矩阵

邻接矩阵分析

操作	复杂度
判断边 \((u,v)\) 是否存在	\(O(1)\)
枚举顶点 \(u\) 的邻接点	\(O(n)\)
空间	\(O(n^2)\)

适合稠密图（dense graph）。

若图很稀疏，矩阵会浪费大量空间。

邻接表

每个顶点保存一组从它出发的邻接边；这组边可以用链表或动态数组等顺序容器来实现。

邻接表分析

操作	复杂度
判断边 \((u,v)\) 是否存在	最坏 \(O(deg(u))\)
枚举顶点 \(u\) 的邻接点	\(O(deg(u))\)
空间	\(O(n+e)\)

适合稀疏图（sparse graph）。

深度优先搜索和广度优先搜索通常优先使用邻接表。

用邻接表实现图的基本操作

现在已经知道邻接表的结构，再看代码中的 adjacency[i] 就不会是一个突然出现的实现细节：它表示顶点 i 的出边表。后面所有遍历和路径算法都会通过同一个 outgoing(i) 接口枚举邻接边。

static final class Graph<Vertex> {
  private final List<Vertex> vertices = new ArrayList<>();
  private final List<List<Edge>> adjacency = new ArrayList<>();

  int addVertex(Vertex vertex) {
    vertices.add(Objects.requireNonNull(vertex, "vertex"));
    adjacency.add(new ArrayList<>());
    return vertices.size() - 1;
  }

  void addDirectedEdge(int from, int to, int weight) {
    checkVertex(from);
    checkVertex(to);
    adjacency.get(from).add(new Edge(from, to, weight));
  }

  void addUndirectedEdge(int a, int b, int weight) {
    addDirectedEdge(a, b, weight);
    addDirectedEdge(b, a, weight);
  }

  int vertexCount() {
    return vertices.size();
  }

  List<Edge> outgoing(int vertex) {
    checkVertex(vertex);
    return Collections.unmodifiableList(adjacency.get(vertex));
  }

  private void checkVertex(int vertex) {
    if (vertex < 0 || vertex >= vertices.size()) {
      throw new IndexOutOfBoundsException(vertex);
    }
  }
}

Graph 把顶点表与邻接表绑定在同一表示中；每条边的端点都必须引用合法顶点。

vertices[i] 与 adjacency[i] 始终描述同一个顶点；两张表按相同索引增长，是邻接表实现最重要的结构不变量。

addVertex(…) 同时追加顶点对象和一条空出边表，并返回这个顶点的稳定编号。

新增顶点后，顶点表和邻接表仍保持一一对应；后面的边都通过这个编号引用顶点。

addDirectedEdge(…) 把一条有向边加入起点的出边表；先检查两个端点，避免边引用图外顶点。

有向边只记录在起点的出边表中，因此枚举某个顶点的后继只需读取这一张表。

addUndirectedEdge(…) 用两个方向的邻接记录表示一条无向边。

这样做以后，后续遍历仍只需要统一处理“从当前顶点出发的邻接边”，不必为无向图再写另一套循环。

vertexCount(…) 直接返回顶点表长度。

顶点编号因此始终是连续的 0..V-1，按顶点分配数组时可以直接用编号作下标。

outgoing(…) 返回当前顶点的只读出边表。

checkVertex(…) 统一检查顶点编号是否合法。

算法可以读取邻接边，但不能绕过 Graph 的操作直接修改内部结构。

进阶表示：什么时候邻接表还不够？

到这里，邻接矩阵和普通邻接表已经足够支撑本章后面的 DFS、BFS、最短路径和拓扑排序。

接下来的三种结构是针对“频繁查入边”或“希望一条边只存一次”等特殊需求，对邻接表做进一步组织。

逆邻接表：把“谁指向我”直接存下来

普通邻接表按起点串起出边；逆邻接表按终点串起入边。它适合反向依赖查询， 但如果同时需要频繁枚举入边和出边，就要维护两套表。

空间仍为 \(O(n+e)\)。

同一条有向边在两套表中各有一个记录：

如果边本身有属性，就存了多份，引入了冗余和潜在冲突！

十字链表

十字链表把两套表合并：每条边只存一次，对边建立链表。

• tail / head：代码中分别表示这条边的起点与终点
• tlink：同一个尾顶点的下一条出边
• hlink：同一个头顶点的下一条入边

从顶点的 firstOut 沿 tlink 枚举出边；从 firstIn 沿 hlink 枚举入边。

十字链表：为什么叫“十字”？

把一条边单独拿出来看，它同时承担两种链表结点的角色：沿 tlink 横向进入同一尾顶点的出边链，沿 hlink 纵向进入同一头顶点的入边链；tail 和 head 则记录这条边的两个端点。

因此“十字”是指同一条边同时被两条链穿过。

邻接多重表：从“一条无向边只建一个结点”理解

先抓住定义：一条无向边只建立一个边结点，但它必须同时出现在两个端点的边表中。

因此边结点保存两个端点：ivex、jvex；并为两个端点各保存一根下一边指针：ilink、jlink。

遍历某个顶点的边表时：当前顶点在 ivex 就沿 ilink，在 jvex 就沿 jlink。两根指针服务于两个端点，不表示固定的几何方向。

三种特化存储：什么时候值得用？

普通邻接表仍然是最常用的默认表示。只有当查询模式很明确时，才值得引入更复杂的结构：

结构	主要解决的问题	适合的场景	代价
逆邻接表	快速枚举“谁指向当前顶点”	反向依赖、频繁查询入边	若同时保留普通邻接表，同一条弧会有两份记录
十字链表	同一条弧既能沿出边链访问，也能沿入边链访问	有向图中入边、出边都需要频繁查询	每个弧结点字段更多，实现更复杂
邻接多重表	无向边只建立一个边结点，却能从两个端点访问	边本身属性较多、希望避免无向边重复存储	遍历时必须判断当前顶点位于 ivex 还是 jvex

选择存储结构的核心不是“哪一种更高级”，而是最常做什么查询，以及是否值得为这些查询承担更复杂的结点结构。

遍历

深度优先搜索：沿一条路走到底，再回退

1. 访问当前顶点
2. 选择一个未访问邻点继续深入
3. 没有未访问邻点时，递归返回并回退
4. 重复，直到当前连通分量全部访问

深度优先搜索：递归实现

static List<Integer> dfs(Graph<?> graph, int start) {
  graph.checkVertex(start);
  boolean[] visited = new boolean[graph.vertexCount()];
  ArrayList<Integer> order = new ArrayList<>(graph.vertexCount());
  dfsVisit(graph, start, visited, order);
  return List.copyOf(order);
}

private static void dfsVisit(
    Graph<?> graph, int vertex, boolean[] visited, List<Integer> order) {
  visited[vertex] = true;
  order.add(vertex);
  for (Edge edge : graph.outgoing(vertex)) {
    if (!visited[edge.to()]) {
      dfsVisit(graph, edge.to(), visited, order);
    }
  }
}

dfs(…) 从起点访问所有可达顶点；visited 保证每个顶点最多被展开一次。

入口只建立一次 visited 和输出序列，然后从起点启动递归；这两份共享状态让所有递归层看到同一套“已发现顶点”。

进入顶点后立刻标记并记录它；因此从任何回边再次遇到该顶点时都能拒绝重复递归，环不会让深度优先搜索无限展开。

只沿尚未访问的出邻点继续递归；每个顶点展开一次、每条邻接边检查一次，所以邻接表实现为 O(V+E)。

深度优先搜索：递归调用栈与复杂度

递归调用栈的变化

执行动作	调用栈变化	为什么
进入 dfs(A)	[A]	A 尚未完成，留在栈中
递归 dfs(B)	[A,B]	A 暂停，继续处理 B
递归 dfs(D)	[A,B,D]	优先把当前分支走到底
D 无路可走	[A,B]	D 出栈，回到最近的未完成调用 B
B 再递归 E	[A,B,E]	回退后继续 B 的下一条未访问邻边

复杂度

图的表示	时间复杂度	原因
邻接表	\(O(n+e)\)	每个顶点访问一次，每条邻接边检查常数次
邻接矩阵	\(O(n^2)\)	每展开一个顶点都要扫描整行

辅助空间：visited 为 \(O(n)\)；最坏情况下递归调用栈深度也是 \(O(n)\)。

广度优先搜索：队列保证逐层扩展

广度优先搜索在发现顶点时立刻标记并入队；之后按先进先出顺序出队。 因此离起点更近的顶点一定先被处理。

广度优先搜索：Java 实现

static List<Integer> bfs(Graph<?> graph, int start) {
  graph.checkVertex(start);
  boolean[] visited = new boolean[graph.vertexCount()];
  ArrayList<Integer> order = new ArrayList<>(graph.vertexCount());
  Deque<Integer> queue = new ArrayDeque<>();
  visited[start] = true;
  queue.offer(start);

  while (!queue.isEmpty()) {
    int vertex = queue.poll();
    order.add(vertex);
    for (Edge edge : graph.outgoing(vertex)) {
      if (!visited[edge.to()]) {
        visited[edge.to()] = true;
        queue.offer(edge.to());
      }
    }
  }
  return List.copyOf(order);
}

bfs(…) 从起点按距离层次访问可达顶点；队列保存下一批尚未展开的顶点。

起点在入队时就标记 visited；“发现即标记”保证同一顶点不会被同层多个前驱重复入队。

先进先出每次取出最早发现的顶点，因此距离起点更近的一层一定先于下一层被处理。

扫描出边时只把未发现邻点标记并入队；每个顶点只入队一次、每条邻接边只检查一次。

队列耗尽意味着从起点可达的所有顶点都已经展开，随后返回本次遍历顺序。

广度优先搜索：队列与复杂度

执行动作	队列变化	含义
A 入队	[A]	起点已发现，等待扩展
A 出队；B、C 入队	[B,C]	第 1 层进入队列
B 出队；D、E 入队	[C,D,E]	C 仍排在更晚发现的 D、E 前面
C 出队	[D,E]	第 1 层全部处理完后才进入第 2 层

表示	时间复杂度	原因
邻接表	\(O(n+e)\)	每个顶点入队一次，每条边检查常数次
邻接矩阵	\(O(n^2)\)	每处理一个顶点都要扫描整行

辅助空间来自 visited 与队列，均为 \(O(n)\)。

非连通图的连通分量

从一个顶点出发的深度优先搜索或广度优先搜索只能访问它所在的连通分量。搜索结束、队列或递归栈为空，并不代表整个图都已经处理完。

因此需要两层结构：内层搜索处理一个完整连通分量，外层 for 再寻找下一个尚未访问的顶点作为新起点。 孤立顶点也会被外层循环单独发现。

非连通图代码

static List<List<Integer>> components(Graph<?> graph) {
  boolean[] visited = new boolean[graph.vertexCount()];
  ArrayList<List<Integer>> result = new ArrayList<>();
  for (int vertex = 0; vertex < graph.vertexCount(); vertex++) {
    if (!visited[vertex]) {
      ArrayList<Integer> component = new ArrayList<>();
      dfsVisit(graph, vertex, visited, component);
      result.add(List.copyOf(component));
    }
  }
  return List.copyOf(result);
}

components(…) 要枚举图中所有连通分量；每次从尚未访问的顶点启动一次完整遍历。

一份全局 visited 跨所有深度优先搜索调用共享；它区分“已经属于某个已发现分量”的顶点与尚未归类的顶点。

外层逐个寻找未访问顶点；每找到一个，就从它启动一次深度优先搜索处理整个连通分量并单独收集。孤立顶点也会自然形成一个单元素分量。

外层扫描结束后每个顶点恰好属于一个已收集分量；返回不可变副本把这次连通分量划分固定下来。

从遍历结果到生成树

回到刚才的 DFS 或 BFS：每当第一次访问一个新顶点时，记录把它带入已访问集合的那条边。起点没有这样的边，其余每个顶点恰好对应一条。

如果原图连通，遍历最终会访问全部 \(n\) 个顶点。除起点外，每个顶点都恰好有一条发现边，所以一共留下 \(n-1\) 条边；沿着“是谁发现我”的关系不断向前追，总能回到起点，因此这些边把所有顶点连在一起。一个含 \(n\) 个顶点、连通且只有 \(n-1\) 条边的无向图必然是一棵树，所以遍历本身就自然产生了一棵生成树。

连通无向图 \(G=(V,E)\) 的生成树是一个包含所有顶点的连通无环子图。

若有 \(n\) 个顶点，任意生成树都有：

\[ n-1 \]

条边。

生成树不唯一。

最小生成树

最小生成树：连接所有顶点，总成本尽量小

一个连通无向图通常有不止一棵生成树。若每条边还带有成本，不同生成树所选的 \(n-1\) 条边不同，总成本也可能不同。

一棵生成树的代价等于树上所有边权之和；其中总代价最小的生成树称为最小生成树（Minimum Spanning Tree，MST）。它解决的是“怎样把所有顶点连起来且总连接成本最低”，不是“从某个起点到某个终点怎样走最短”。

常用算法有 Kruskal 和 Prim：前者从全局最轻的边开始筛选，后者从一棵只含起点的小树开始向外扩展。

割性质：跨过一个割时，最轻边为什么安全？

把顶点集合分成两个非空部分 \(S\) 和 \(V-S\)，就得到一个割（cut）；连接两侧顶点的边称为跨割边。

对于与当前已选森林相容的割，跨割边中权值最小的边是一条安全边（safe edge）：它可以加入当前森林，而不会失去得到某棵最小生成树的可能。

交换论证说明了原因：若某棵最小生成树没有选择这条最轻边 \(e\)，把 \(e\) 加进去会产生一个环；这个环必然还包含另一条跨割边 \(f\)。因为 \(w(e)\le w(f)\)，删掉 \(f\)、保留 \(e\) 后仍是生成树，而且总代价不会变大。

Kruskal 思路：从最便宜的边开始，但不能成环

如果只按边权从小到大不停加入边，迟早可能把已经连通的顶点再次接起来，形成环；这样的边不会帮助我们连接新的顶点。

Kruskal 因此维护一片“生成森林”：

1. 先把所有边按权值从小到大排序；
2. 依次检查当前最轻的边；
3. 如果它连接的是两个不同连通分量，就接受这条边并合并两个分量；
4. 如果两个端点已经连通，加入它只会形成环，就跳过；
5. 选到 \(n-1\) 条边时，生成树完成。

第 7 章学过的并查集正好可以快速回答“两个端点是否已经属于同一个连通分量”。Kruskal 每次接受的边，都可以看成某个割上的最轻跨割边，因此由割性质保证安全。

Kruskal 图解：按边权扫描并避免成环

Kruskal 代码

static List<Edge> kruskal(List<Edge> edges, int vertexCount) {
  if (vertexCount < 0) {
    throw new IllegalArgumentException("vertexCount must be non-negative");
  }
  ArrayList<Edge> sorted = new ArrayList<>(edges);
  sorted.sort(Comparator.comparingInt(Edge::weight));
  DisjointSet ds = new DisjointSet(vertexCount);
  ArrayList<Edge> tree = new ArrayList<>(Math.max(0, vertexCount - 1));
  for (Edge edge : sorted) {
    Objects.checkIndex(edge.from(), vertexCount);
    Objects.checkIndex(edge.to(), vertexCount);
    if (ds.union(edge.from(), edge.to())) {
      tree.add(edge);
      if (tree.size() == vertexCount - 1) {
        break;
      }
    }
  }
  if (vertexCount > 0 && tree.size() != vertexCount - 1) {
    throw new IllegalArgumentException("graph is disconnected");
  }
  return List.copyOf(tree);
}

kruskal(…) 按边权从小到大选边；并查集用来判断加入当前边是否会形成环。

排序把候选边固定为从轻到重的单调扫描，并让每个顶点先自成连通分量；当前已选边因此始终是一片生成森林。

每条边只有连接两个不同连通分量时才会被 union 接受，所以森林始终无环。当前最轻的跨割边可作为安全边（safe edge）；其依据是割性质（cut property）。达到 V-1 条即可结束。

若扫描完仍不足 V-1 条，图不连通；成功时“无环且 V-1 条”保证得到生成树，而每一步选择安全边才保证最小总权重。

Kruskal 分析

若边数为 \(e\)，顶点数为 \(n\)：

• 边排序：\(O(e\log e)\)
• 并查集初始化：\(O(n)\)
• 最多 \(e\) 次 union/find：均摊 \(O(e\alpha(n))\)

因此更完整地写为：

\[ O\!\left(e\log e + e\alpha(n) + n\right) \]

比较排序（comparison sort）通常由 \(e\log e\) 主导，所以常简写为 \(O(e\log e)\)。

适合边较少的稀疏图。

Prim 思路：让一棵树从一个起点向外生长

Kruskal 是“全局看边”；Prim 换一个视角：始终维护一棵已经连通的树。设 \(U\) 是已经进入生成树的顶点集合，\(V-U\) 是树外顶点。

每一轮只做两件事：

1. 在所有“连接树内顶点与树外顶点”的边中，选择权值最小的一条；
2. 用这条边把一个新顶点接入 \(U\)，再更新树外顶点连接当前树的最便宜方式。

因为每轮都只接入一个原本在树外的新顶点，所以当前结构始终连通，而且不会因为这一步形成环。这里同样使用刚才的割性质：当前树 \(U\) 与树外 \(V-U\) 之间的最轻边可以安全地加入某棵最小生成树。

Prim 的状态：lowcost 和 nearvex

状态	含义
inTree[i]	顶点 i 是否已经进入当前生成树
lowcost[i]	树外顶点 i 连接当前生成树时，已知的最小边权
nearvex[i]	哪个树内顶点提供了这条最小边

当一个新顶点进入 \(U\) 后，把 inTree[i] 设为真；随后只需检查它到各树外顶点的边。如果出现更便宜的连接，就同时更新 lowcost 和 nearvex。

Prim 图解：每次把一个树外顶点接进来

Prim：Java 实现

static List<Edge> prim(Graph<?> graph, int start) {
  graph.checkVertex(start);
  int n = graph.vertexCount();
  boolean[] inTree = new boolean[n];
  long[] lowcost = new long[n];
  int[] nearvex = new int[n];
  Arrays.fill(lowcost, INF);
  Arrays.fill(nearvex, -1);
  lowcost[start] = 0;
  ArrayList<Edge> tree = new ArrayList<>(Math.max(0, n - 1));

  for (int added = 0; added < n; added++) {
    int next = -1;
    for (int vertex = 0; vertex < n; vertex++) {
      if (!inTree[vertex]
          && (next == -1 || lowcost[vertex] < lowcost[next])) {
        next = vertex;
      }
    }
    if (next == -1 || lowcost[next] == INF) {
      throw new IllegalArgumentException("graph is disconnected");
    }
    inTree[next] = true;
    if (nearvex[next] != -1) {
      tree.add(new Edge(nearvex[next], next, Math.toIntExact(lowcost[next])));
    }
    for (Edge edge : graph.outgoing(next)) {
      if (!inTree[edge.to()] && edge.weight() < lowcost[edge.to()]) {
        lowcost[edge.to()] = edge.weight();
        nearvex[edge.to()] = next;
      }
    }
  }
  return List.copyOf(tree);
}

prim(…) 从一个起点开始维护当前生成树，并逐步把树外顶点接进来。

初始化 inTree、lowcost 和 nearvex：起点的接入代价为 0，其余顶点暂时为无穷大。

每一轮先选出 lowcost 最小的树外顶点并加入对应安全边，再用新顶点的邻边更新其余候选；若最小值仍为无穷大，说明原图不连通。

所有顶点都进入树后，返回已经选出的 V-1 条最小生成树边。

Prim 复杂度

• 邻接矩阵实现：每轮线性寻找最小 lowcost，总时间 \(O(n^2)\)；
• 邻接表配合最小堆：可做到 \(O(e\log n)\) 量级，更适合稀疏图。

最小生成树不唯一

若图中存在多条相同权值边，最小生成树可能不唯一。

只要总权重相同且满足生成树条件，多个答案都可能正确。

Kruskal 和 Prim 在相同权边的选择顺序不同，可能得到不同的最小生成树。

最短路径

最短路径问题：从一个起点出发，怎样让总代价最低？

把顶点看成地点，把边权看成走过一条边需要付出的代价。现在从源点 A 出发，希望得到 A 到每个可达顶点的最低总代价。

先分析：哪个暂定距离可以放心确定？

维护 dist[v]：目前已经找到的 A 到 v 的最小候选距离。开始时只有 dist[A]=0，其余都是 \(\infty\)。

假设当前尚未确定的顶点里，u 的 dist[u] 最小。因为所有边权都非负，所以任何“先绕到别的未确定顶点、再回来”的路径，都不可能把 u 的总代价降到当前值以下。

因此可以做三件事：

1. 选出尚未确定顶点中 dist 最小的 u；
2. 把 u 的距离标记为最终值；
3. 用 u 的出边尝试改进邻点：dist[v] = min(dist[v], dist[u] + w(u,v))。

这种“发现一条更短的走法，就把当前距离改小”的操作称为松弛（relaxation）。

这个“取当前最小候选并永久确定”的贪心过程，就是 Dijkstra 算法。

Dijkstra：取最小、确定与松弛

每一轮要严格区分两个动作：先从未确定顶点中选出 dist 最小者，并把它的距离变成最终值；下一步才从这个顶点向外扫描边并做松弛。确定只改变“是否确定”，松弛才可能改变其他顶点的 dist 和前驱。

Dijkstra：Java 实现

static long[] dijkstra(Graph<?> graph, int source) {
  graph.checkVertex(source);
  long[] distance = new long[graph.vertexCount()];
  Arrays.fill(distance, INF);
  PriorityQueue<State> queue =
      new PriorityQueue<>(Comparator.comparingLong(State::distance));
  distance[source] = 0;
  queue.offer(new State(source, 0));

  while (!queue.isEmpty()) {
    State current = queue.poll();
    if (current.distance() != distance[current.vertex()]) {
      continue;
    }
    for (Edge edge : graph.outgoing(current.vertex())) {
      if (edge.weight() < 0) {
        throw new IllegalArgumentException("Dijkstra requires non-negative edge weights");
      }
      long candidate = current.distance() + edge.weight();
      if (candidate < distance[edge.to()]) {
        distance[edge.to()] = candidate;
        queue.offer(new State(edge.to(), candidate));
      }
    }
  }
  return distance;
}

方法返回源点到所有顶点的最短距离；贪心“确定”只在所有边权非负时成立。

初始化令 dist[source]=0、其余为 INF，并把源点作为唯一初始候选放入最小优先队列。

先取出当前最小候选 A，并确认它不是过期条目；这一阶段只对应“确定”。

确定 A 之后才扫描 A 的出边；松弛只会修改邻点的暂定距离。

下一轮取出当前最小候选 C，并把 dist[C] 确定下来。

再展开 C；B、D、E 的暂定距离可能在这一阶段被改进。

取出 B 并确定 dist[B]；此时还没有扫描 B 的出边。

展开 B，用 B 的出边继续改进树外候选。

取出 D 并确定 dist[D]。

展开 D，更新 E 和 F 的暂定距离。

取出 E 并确定 dist[E]。

展开 E，把 F 的候选从 14 改进为 11。

取出最后一个有限候选 F 并确定 dist[F]。

最后展开 F；没有邻边能够继续改进距离。

优先队列耗尽后返回最终距离数组；不可达顶点仍保持 INF。

Dijkstra 的适用范围与复杂度

Dijkstra 的关键前提不是“图必须有向或无向”，而是：从源点可达的边权不能为负。 只有这样，“当前最小候选可以永久确定”这一步才成立。

图表示 / 数据结构	时间	额外空间
邻接矩阵 + 线性扫描	\(O(n^2)\)	\(O(n)\)
邻接表 + 支持减小键值的二叉堆	\(O((n+e)\log n)\)	\(O(n)\)
邻接表 + 惰性 PriorityQueue (示例代码)	\(O((n+e)\log e)\)	\(O(n+e)\)

示例代码不主动删除旧候选，而是把更短的新候选再次入队，再用过期检查忽略旧条目，所以队列最坏可保存 \(O(e)\) 个状态。

如果边权允许为负，会发生什么？

考虑三条有向边：A→B 的权值为 2，A→C 的权值为 5，C→B 的权值为 -6。

如果仍按 Dijkstra 的规则，B=2 会比 C=5 更早被“确定”；但后来经过 C 可以得到 A→C→B，总代价是 \(5+(-6)=-1\)。原来已经确定的 B 又变短了。

因此存在负权边时，不能再把当前最小候选直接当作最终值。我们需要允许一个顶点的距离在后续继续被改进。

重新分析：让更短的路径一轮一轮传播

仍然维护 dist[v]，但不再区分“已确定”和“未确定”。一轮轮检查：

\[ dist[v] \leftarrow \min\bigl(dist[v],\;dist[u]+w(u,v)\bigr) \]

把所有边完整扫描一轮以后：所有“最短走法至多使用 1 条边”的顶点，已经得到正确距离

扫描两轮后，至少覆盖至多 2 条边的最短走法。

如果不存在从源点可达的负环，最短简单路径最多经过 \(n-1\) 条边，所以最多做 \(n-1\) 轮就足够。

完成这 \(n-1\) 轮后再额外扫描一遍；如果仍能把某个距离改小，就说明存在从源点可达的负环，此时受它影响的顶点不存在有限的最短距离。

Bellman-Ford 图解：完整一轮松弛

注意：一轮内的更新可能沿边的扫描顺序继续传播；正确性边界仍是“做满 \(n-1\) 轮”。

Bellman-Ford：逐轮松弛与负环检查

static BellmanFordResult bellmanFord(List<Edge> edges, int vertexCount, int source) {
  Objects.checkIndex(source, vertexCount);
  long[] distance = new long[vertexCount];
  Arrays.fill(distance, INF);
  distance[source] = 0;

  for (int pass = 1; pass < vertexCount; pass++) {
    boolean changed = false;
    for (Edge edge : edges) {
      Objects.checkIndex(edge.from(), vertexCount);
      Objects.checkIndex(edge.to(), vertexCount);
      if (distance[edge.from()] == INF) {
        continue;
      }
      long candidate = distance[edge.from()] + edge.weight();
      if (candidate < distance[edge.to()]) {
        distance[edge.to()] = candidate;
        changed = true;
      }
    }
    if (!changed) {
      break;
    }
  }

  boolean negativeCycle = false;
  for (Edge edge : edges) {
    if (distance[edge.from()] != INF
        && distance[edge.from()] + edge.weight() < distance[edge.to()]) {
      negativeCycle = true;
      break;
    }
  }
  return new BellmanFordResult(distance, negativeCycle);
}

bellmanFord(…) 允许负权边，通过最多 V-1 轮松弛传播最短路估计，并再检查负环。

先把源点距离设为 0，其余为 INF；这表示当前只知道长度为 0 的路径，后续每一轮再允许最短路多使用一条边。

每轮完整扫描所有边：不可达前缀不能产生候选；可达前缀则尝试松弛。做满 V-1 轮即可覆盖任何简单最短路径。

若一整轮没有任何距离变短，说明所有边都已经无法继续改进当前距离；后面再扫描也不会产生更短路径，因此可以提前结束。

正常轮次结束后再扫一次可达边；若仍能松弛，就意味着还能无限借助某个可达负环降低路径代价。

结果同时返回距离表与负环标志：前者描述当前最短路，后者告诉调用者这些距离是否被可达负环破坏了有限最优值语义。

最后一轮检查能告诉我们什么？

完成 \(n-1\) 轮后再扫描所有边，如果某条从源点可达的边仍然可以松弛，就能确定：至少存在一个从源点可达的负环，继续绕这个环会让路径代价不断下降。

但这次额外扫描只回答“是否还存在可改进”，不会自动把每个负环逐一列出来；而且从当前源点不可达的负环不会影响这次单源最短路，也不会被这个检测发现。

如果要输出所有负环

以上一页的图为例，若要求枚举其中所有简单负环，输出应包括：\(B\to C\to B\)（权值和 \(-2\)）与 \(D\to E\to F\to D\)（权值和 \(-2\)）。

Bellman-Ford 最常见的扩展是恢复一个可达负环：松弛时记录前驱；在额外一轮中记住仍被更新的顶点 \(x\)，沿前驱连续走 \(n\) 次可以进入某个环内，再继续沿前驱直到回到起点，就能输出这个负环。

如果要求枚举图中的所有简单负环，问题会更难：

1. 先找出需要考虑的强连通分量；若讨论某个源点的最短路，只保留从源点可达的部分；
2. 在每个可能含环的强连通分量中枚举简单环；
3. 计算每个环的权值和，只输出权值和小于 0 的环。

一张图可能含有指数数量的简单环，因此“输出所有负环”的运行时间至少受输出规模限制；它不是标准 Bellman-Ford 的直接输出。实际最短路程序通常只需要判断是否存在可达负环，或恢复一个负环作为证据。

Bellman-Ford 复杂度

• 时间：最多 \(n-1\) 轮，每轮扫描 \(e\) 条边，故为 \(O(ne)\)
• 额外空间：本实现只有 distance 等按顶点数组，为 \(O(n)\)；若额外保存前驱，再增加一个 \(O(n)\) 数组
• 若某一整轮 changed=false，可以提前结束，但最坏情况不变

如果要一次得到任意两点之间的最短距离呢？

前面的问题都固定一个源点。若现在要同时回答任意 \(i\) 到任意 \(j\) 的最短距离，一个直接办法是：把每个顶点都当一次源点，反复运行单源最短路径算法。

这当然可行，但它把同一张图反复处理了很多遍。若图本来就用邻接矩阵表示，并且确实需要完整的 \(n\times n\) 距离表，可以换一个整体视角：直接维护所有点对的距离矩阵。

新的问题变成：当允许一个新的顶点 \(k\) 作为中间点时，哪些点对会变短？

重新分析：逐步扩大“允许的中间点集合”

先建立距离矩阵 dist[i][j]：有直接边时填边权，i=j 时填 0，没有已知路径时填 \(\infty\)。

接下来按某个顶点顺序逐个放宽限制。假设当前把顶点 \(k\) 新加入允许的中间点集合。对任意起点 \(i\) 和终点 \(j\)，只需要比较两种情况：

1. 不经过 \(k\)，继续使用原来的 dist[i][j]；
2. 经过 \(k\)，先走到 \(k\)，再从 \(k\) 走到 \(j\)，总代价是 dist[i][k] + dist[k][j]。

因此每个格子都用同一条规则更新：

\[ dist[i][j]\leftarrow\min\bigl(dist[i][j],\;dist[i][k]+dist[k][j]\bigr) \]

当所有顶点都已经允许作为中间点时，矩阵就给出了任意两点之间的最短距离。这个动态规划就是 Floyd 算法。

Floyd 图解：一个中间点怎样改进整张矩阵

每一轮只新增一个可用中间点，但会检查所有起点和终点组合。对每一对顶点，都比较“保持原来的最短距离”与“经过当前中间点”这两种选择。

Floyd：\(k\) 必须是最外层循环

static void floyd(long[][] distance) {
  int n = distance.length;
  for (long[] row : distance) {
    if (row.length != n) {
      throw new IllegalArgumentException("distance matrix must be square");
    }
  }
  for (int middle = 0; middle < n; middle++) {
    for (int from = 0; from < n; from++) {
      if (distance[from][middle] == INF) {
        continue;
      }
      for (int to = 0; to < n; to++) {
        if (distance[middle][to] == INF) {
          continue;
        }
        long throughMiddle = distance[from][middle] + distance[middle][to];
        if (throughMiddle < distance[from][to]) {
          distance[from][to] = throughMiddle;
        }
      }
    }
  }
}

floyd(…) 逐个允许中间顶点加入路径；第 k 轮后矩阵只使用前 k 个中间点。

Floyd 的状态是一张全点对距离矩阵，因此首先要求它是方阵；每个下标必须同时能作为源点、终点和中间点。

middle 必须是最外层阶段：进入这一轮时，矩阵已经允许更早的中间点；若 from→middle 不可达，就无需枚举任何终点。

对每个终点，只有 middle→to 也可达时，才存在 from→middle→to 这条合法候选路径。

每个点对只在“经过当前 middle 更短”时更新；一轮结束后，矩阵就精确表示允许使用到当前 middle 为止的全部最短路径。

Floyd 复杂度与负环判断

• 时间：三重循环 \(O(n^3)\)
• 距离矩阵本身占 \(O(n^2)\)；本实现原地更新该输入矩阵，除循环变量外额外空间为 \(O(1)\)
• 若另存路径重建信息或 next 矩阵，则再需要 \(O(n^2)\)
• 算法结束后若存在 dist[v][v] < 0，说明图中存在负环

拓扑排序

依赖问题：哪些任务现在已经可以执行？

在构建系统或课程先修关系中：

• 顶点表示一个任务或一门课程
• 有向边 \(u\to v\) 表示“完成 \(u\) 后才能开始 \(v\)”
• 目标是找到一个线性序列，使每条边的起点都出现在终点之前

这类有向图常称为顶点活动网。只有有向无环图才可能给出覆盖全部顶点的拓扑序。

拓扑排序思路：入度为 0 的顶点没有未完成前置条件

维护每个顶点的入度，以及一个保存“当前入度为 0 的顶点”的队列：

1. 将当前所有入度为 0 的顶点入队
2. 从队首取出一个顶点 \(u\) 并输出
3. 删除 \(u\) 的所有出边，让每个后继的入度减 1
4. 某个后继的入度变为 0 时，立即入队

不变量：队列中的每个顶点，其所有前驱都已经输出。

拓扑排序图解：删除约束，释放后继

同一时刻若有多个入度为 0 的顶点，选择顺序可以不同，所以拓扑序通常不唯一。

拓扑排序：Java 实现

static List<Integer> topologicalSort(Graph<?> graph) {
  int[] indegree = new int[graph.vertexCount()];
  for (int vertex = 0; vertex < graph.vertexCount(); vertex++) {
    for (Edge edge : graph.outgoing(vertex)) {
      indegree[edge.to()]++;
    }
  }

  Deque<Integer> queue = new ArrayDeque<>();
  for (int vertex = 0; vertex < indegree.length; vertex++) {
    if (indegree[vertex] == 0) {
      queue.offer(vertex);
    }
  }

  ArrayList<Integer> order = new ArrayList<>(graph.vertexCount());
  while (!queue.isEmpty()) {
    int vertex = queue.poll();
    order.add(vertex);
    for (Edge edge : graph.outgoing(vertex)) {
      if (--indegree[edge.to()] == 0) {
        queue.offer(edge.to());
      }
    }
  }
  if (order.size() != graph.vertexCount()) {
    throw new IllegalStateException("graph has a directed cycle");
  }
  return List.copyOf(order);
}

topologicalSort(…) 反复取入度为 0 的顶点；若最后仍有顶点未输出，图中就存在有向环。

先统计每个顶点尚未满足的前驱数量；indegree[v] 始终表示“还有多少前置任务尚未完成”。

初始所有入度为 0 的顶点都进入队列；这些顶点已经没有未完成的前置条件。

输出一个顶点等价于删除它的所有出边；某个后继入度降到 0 时，说明最后一个前置条件刚刚解除。

若队列已经空却仍有顶点未输出，剩余顶点都还有前驱，说明依赖关系中存在有向环。

所有顶点都成功输出时，返回序列就是一个合法拓扑序。

拓扑排序：队列、入度与环检测

队列保存的不是“下一层”，而是“现在已经可以执行”的任务。

时刻	队列	发生了什么
初始	A	A 的入度为 0，可以直接执行
输出 A	B, C	删除 A 的出边，B、C 的入度降到 0
输出 B	C	D 仍有来自 C 的前置条件，不能入队
输出 C	D	D 的最后一个前置条件解除

若队列已经为空，但仍有顶点没有输出，则这些剩余顶点的入度都大于 0：它们互相等待，图中存在有向环，因此不存在完整拓扑序。

使用邻接表时，每个顶点入队至多一次，每条边只在其起点被输出时处理一次，所以时间复杂度为 \(O(n+e)\)，额外空间为 \(O(n)\)。

关键路径

项目调度问题：项目最早多久能完成？

一个项目由若干活动组成，有些活动可以并行，有些活动必须等待前置工作完成后才能开始。下面每条有向边代表一项活动，数字是完成这项活动所需的时间。

现在先回答两个实际问题：

1. 如果所有活动都尽早开始，项目最早什么时候能完成？
2. 哪些活动一旦延迟，就一定会推迟整个项目？

把项目约束写成边活动网

标准模型：网络是有向无环图，并且只有一个项目开始事件和一个项目完成事件。 事件本身不消耗时间；一个事件只有在所有指向它的前置活动都完成后才发生。

顶点表示里程碑事件，边表示活动，边权表示活动持续时间。

即使 C→D 很早完成，只要 B→D 还没有结束，D 就不能发生。因此 D 的最早发生时间不能取前驱中的最小值，而必须等待最慢的那一条前置链。

先正向推：每个事件最早什么时候能发生？

为了让公式尽量简短，用 \(E[v]\) 表示事件 \(v\) 的最早发生时刻。

项目开始事件的最早时刻为 0。对每条活动 \(u\to v\)，若活动持续时间为 \(w\)，那么事件 \(v\) 至少要等到事件 \(u\) 发生后再经过 \(w\) 个时间单位：

\[ E[v]=\max_{(u,v,w)}\bigl(E[u]+w\bigr) \]

必须沿拓扑序正向计算，因为计算事件 \(v\) 之前，要先知道所有前驱事件 \(u\) 的最早时刻。取最大值不是在“拖慢项目”，而是在表达：汇合点必须等待所有前置活动都完成。

再反向问：每个事件最晚可以拖到什么时候？

知道项目最早完成时刻后，再从汇点向源点反推。用 \(L[v]\) 表示事件 \(v\) 的最晚允许发生时刻；超过这个时刻，就会推迟整个项目。

汇点的 \(L\) 等于项目工期。对活动 \(u\to v\)，如果事件 \(v\) 最晚在 \(L[v]\) 发生，那么事件 \(u\) 最晚只能到 \(L[v]-w\)。一个事件可能有多个后继，所以要同时满足所有后继限制：

\[ L[u]=\min_{(v,w)}\bigl(L[v]-w\bigr) \]

这一步要按逆拓扑序计算。正向取最大值，是因为前置活动必须全部完成；反向取最小值，是因为后继限制必须全部满足。

关键路径图解：最早时刻、最晚时刻与时差

计算顺序是：先沿拓扑序正向得到各事件的 \(E[v]\)，再按逆拓扑序反向得到 \(L[v]\)，最后比较每条活动的最早开始与最晚开始。二者相等时，这条活动没有任何可延迟余量。

从事件时间推出活动时差

对活动边 \(a=(u,v,w)\)：

\[ e(a)=E[u], \qquad l(a)=L[v]-w \]

活动时差为：

\[ slack(a)=l(a)-e(a) \]

以图中的 \(B\to D\)（持续时间 4）为例，\(E[B]=3\)、\(L[D]=7\)，所以：

\[ e=3, \qquad l=7-4=3, \qquad slack=0 \]

这项活动没有延迟空间，因此是关键活动。把从项目起点到终点、连续由关键活动组成的一条完整链称为关键路径。零时差活动可能分布在多条关键路径上，所以“所有关键活动的集合”不一定只形成一条路径。

关键路径：正向计算、反向计算与时差

static CriticalPathResult criticalPath(Graph<?> graph) {
  List<Integer> topologicalOrder = topologicalSort(graph);
  if (graph.vertexCount() == 0) {
    throw new IllegalArgumentException("AOE network must contain at least one event");
  }
  int[] indegree = new int[graph.vertexCount()];
  int sink = -1;
  int sinkCount = 0;
  for (int vertex = 0; vertex < graph.vertexCount(); vertex++) {
    List<Edge> outgoing = graph.outgoing(vertex);
    if (outgoing.isEmpty()) {
      sink = vertex;
      sinkCount++;
    }
    for (Edge edge : outgoing) {
      indegree[edge.to()]++;
    }
  }
  int sourceCount = 0;
  for (int degree : indegree) {
    if (degree == 0) {
      sourceCount++;
    }
  }
  if (sourceCount != 1 || sinkCount != 1) {
    throw new IllegalArgumentException(
        "AOE network must have exactly one source and one sink");
  }
  long[] earliest = new long[graph.vertexCount()];
  for (int vertex : topologicalOrder) {
    for (Edge edge : graph.outgoing(vertex)) {
      if (edge.weight() < 0) {
        throw new IllegalArgumentException("activity duration must be non-negative");
      }
      earliest[edge.to()] =
          Math.max(earliest[edge.to()], earliest[vertex] + edge.weight());
    }
  }

  long projectDuration = earliest[sink];
  long[] latest = new long[graph.vertexCount()];
  Arrays.fill(latest, projectDuration);
  for (int index = topologicalOrder.size() - 1; index >= 0; index--) {
    int vertex = topologicalOrder.get(index);
    for (Edge edge : graph.outgoing(vertex)) {
      latest[vertex] = Math.min(latest[vertex], latest[edge.to()] - edge.weight());
    }
  }

  ArrayList<Activity> activities = new ArrayList<>();
  ArrayList<Edge> criticalEdges = new ArrayList<>();
  for (int vertex : topologicalOrder) {
    for (Edge edge : graph.outgoing(vertex)) {
      long earliestStart = earliest[vertex];
      long latestStart = latest[edge.to()] - edge.weight();
      long slack = latestStart - earliestStart;
      activities.add(new Activity(edge, earliestStart, latestStart, slack));
      if (slack == 0) {
        criticalEdges.add(edge);
      }
    }
  }
  return new CriticalPathResult(
      earliest.clone(),
      latest.clone(),
      projectDuration,
      List.copyOf(activities),
      List.copyOf(criticalEdges));
}

criticalPath(…) 在边活动网中计算事件最早/最迟时刻，并用时差为 0 找出关键活动。

先要求图可拓扑排序且非空；关键路径建立在有向无环的边活动网上，空网络没有可解释的项目起点、终点或工期。

扫描整张图统计入度和汇点数量；这一步不是在算时间，而是在识别“没有前驱的源点”和“没有后继的汇点”。

标准边活动网要求源点和汇点各恰好一个；若不满足，就不能把某一条源点到汇点的最长路径直接解释成整个项目工期。

沿拓扑序正向取最大值，earliest[v] 表示所有前驱活动都完成后事件 v 最早何时发生；负持续时间会破坏这一时间模型，必须拒绝。

汇点的最早发生时间就是项目最短工期；从该工期逆拓扑取最小值，得到每个事件在不延误项目时允许的最迟发生时间。

活动的最早开始时间来自起点事件，最迟开始时间来自终点事件的最迟发生时间减去持续时间；时差为 0 的活动就是关键活动。

最终一起返回最早/最迟时间、总工期、全部活动和零时差边；调用者由此同时得到调度余量与关键路径结构。

关键路径复杂度与前提

• 拓扑排序：\(O(n+e)\)
• 正向 / 反向扫描：每个顶点、边各处理常数次，\(O(n+e)\)
• 时差扫描：\(O(e)\)
• 总时间：\(O(n+e)\)；额外空间：\(O(n)\)（不计图本身的存储）

若边活动网存在环，拓扑序不存在，\(E/L\) 的递推也就没有合法计算顺序。

把算法放回它解决的问题中

算法	核心状态 / 不变量	必要条件	主要输出
深度优先搜索	递归调用栈；沿路深入	无	遍历序列 / 连通分量
广度优先搜索	先进先出队列；按无权距离分层	无	遍历序列 / 无权最短距离
Dijkstra	已确定集合；最小暂定距离	边权非负	单源最短路径
Bellman-Ford	第 \(k\) 轮传播至多 \(k\) 条边	不存在从源点可达的负环	单源最短路径
Floyd	允许的中间点集合逐轮扩大	不存在负环	全点对最短路径

先识别问题与前提条件，再选算法；只背循环结构无法判断算法是否适用。

有向无环图上的两个问题共享拓扑序

算法	核心状态 / 不变量	必要条件	主要输出
拓扑排序	零入度队列	有向无环图	满足依赖关系的执行顺序
关键路径	拓扑序上正向算 \(E\)、反向算 \(L\)	边活动网且无环	总工期 / 零时差活动

拓扑排序先建立合法依赖顺序；关键路径再利用这个顺序做动态规划。

表示方式改变成本，不改变算法语义

操作模式	邻接表	邻接矩阵
枚举稀疏邻点	\(O(deg(v))\)，自然	必须扫整行 \(O(n)\)
查询边是否存在	最坏 \(O(deg(v))\)	\(O(1)\)
图存储	\(O(n+e)\)	\(O(n^2)\)
典型算法	深度优先搜索、广度优先搜索、堆优化 Dijkstra、拓扑排序	稠密图 Prim、线性扫描 Dijkstra、Floyd

同一个不变量可以落在不同表示上；差异来自“找邻点 / 找最小候选 / 更新矩阵” 这些基本操作的成本。

本章小结

• 图由顶点与边描述关系；有向、无向、带权、连通等术语决定后续问题形式。
• 邻接矩阵适合快速判断边和稠密图，邻接表及其变体适合枚举稀疏邻点和保存复杂边关系。
• 深度优先搜索、广度优先搜索、连通分量和生成树都围绕“已访问”不变量展开，只是推进顺序不同。
• Kruskal 按边权扩展并用并查集防止成环，Prim 从一个顶点集合出发不断选择跨割最小边。
• Dijkstra、Bellman-Ford 和 Floyd 分别对应非负单源、允许负边单源和全点对最短路径场景。
• 拓扑排序要求有向无环图；顶点活动网用入度变化表达先修约束和可执行顺序。
• 边活动网把活动放在边上，用最早/最迟时间识别时差为零的关键活动与关键路径。

下载本章完整 Gradle 工程

本章习题

• 习题 1：无向连通图性质：含 \(n\) 个顶点的无向连通图至少需要多少条边？若恰有该数量的边，图具有什么结构？
• 习题 2：错误的最短路贪心：分析“每次从当前顶点选择最近的未访问邻接点”这一贪心策略能否保证得到最短路径；若不能，给出反例。
• 习题 3：拓扑排序：说明拓扑序与有向环之间的关系，并讨论拓扑序是否一定唯一。
• 习题 4：Kruskal 与 Prim：比较 Kruskal 与 Prim 构造最小生成树的选择规则、所需辅助结构，并说明何时最小生成树唯一。

致谢

谢谢

sqlite@nju.edu.cn
https://slab-nju.cn

石守谦