🕸️ 图

click a node, then bfs or dfs

click two nodes to pick start and goal

paint some walls, then run BFS

press run to compute boot order

press iterate to relax the graph

click nodes to add or remove anchors

动手试试：一个演示，六种模式。traverse（遍历）：把边界分别可视化成队列和栈，对比 BFS 与 DFS——点击任意节点设为起点，然后让两者同场竞速。shortest path（最短路径）：选起点 + 终点，在带权图上比较 Dijkstra 与 A*。grid（网格）：刷上墙壁，看 BFS 绕开它们规划。dag · topo：给机器人启动序列排序；制造一个环，看算法拒绝执行。pose graph（位姿图）：借助一个回环约束，把一条漂移的轨迹松弛回来（玩具版 SLAM）。coverage（覆盖）：撒下若干锚点，得到一张离散 Voronoi 图。

为什么它重要

图为各种关系建模：社交网络、道路地图、依赖关系、状态机。BFS 找最短路径，DFS 探索所有可能。图是连通数据的通用语言。

核心思想

想象一张由道路连接各城市的地图。每个城市是一个顶点（节点），每条道路是一条边（连接）。

图可以是：

• 有向的：单行道（Twitter 的关注）
• 无向的：双向路（Facebook 的好友）
• 带权的：带有距离的道路

两种表示法：

1. 邻接矩阵：一个二维数组，若边存在则 matrix[i][j] = 1。查找快，O(1)，但空间 O(V^2)。
2. 邻接表：每个顶点存一张它的邻居列表。省空间，O(V+E)。

两种遍历：

• BFS：逐层探索，像池塘里的涟漪。能找到（无权图的）最短路径。
• DFS：尽可能往深处走，然后回溯。可检测环、做拓扑排序。

要点回顾

• 顶点（节点）+ 边（连接）
• 邻接表通常更省空间
• BFS 找最短路径，用队列
• DFS 往深处探索，用栈（或递归）

再深入一些

拓扑排序 —— Kahn 算法与 DFS 完成时间

DAG（有向无环图）表示的是依赖关系。拓扑排序把 DAG 线性化，使每条边 u → v 在输出中 u 都出现在 v 之前——也就是说，每个依赖项都排在依赖它的项之前。两种算法，都是 O(V + E)：

Kahn 算法（用于演示的 dag · topo 模式）：

1. Compute in-degree for every node.
2. Enqueue all nodes with in-degree 0 (no dependencies).
3. While the queue is non-empty:
     u = dequeue.  emit(u).
     For each edge u → v:
       in-degree[v] -= 1
       if in-degree[v] == 0: enqueue(v).
4. If emitted fewer than V nodes → the graph contains a cycle.

DFS 完成时间变体： 从每个未访问的节点出发跑 DFS；当一个节点完成时（它的所有后代都已探索完毕），把它压入一个栈。逆序弹出栈即得拓扑序。这个变体能自然地扩展去求强连通分量（Kosaraju、Tarjan）——其应用包括在社交图中找出聚类、分析程序控制流。

机器人中的用途： ROS launch 文件构成一个 DAG（每个节点都有必须先启动的前置节点）；启动系统在底层做的就是拓扑排序。行为树和 Make/Bazel 构建图也是同一个形状。

Bellman-Ford —— Dijkstra 那位能处理负权的表亲

Dijkstra 假定边权非负。它的正确性证明依赖于这样一个事实：一旦你以当前最小代价从优先队列中弹出一个节点，之后就不可能再有更短的路径抵达它。负权打破了这个假设——一条长但便宜的绕路，可能缩短一条已经"敲定"的路径。

Bellman-Ford 以速度换取处理负权的能力：

For each of V−1 iterations:
  For each edge (u, v, w):
    if dist[u] + w < dist[v]: dist[v] = dist[u] + w

这是 O(V·E)——远比带堆的 Dijkstra 的 O((V+E) log V) 慢。回报是在负权下的正确性，外加检测负环的能力（第 V 次迭代仍能松弛某条边，就意味着存在一个总权重为负的环——你的最短路径会永远绕圈）。

何时需要它： 货币套利检测、带过路费返还/补贴的路线规划，以及任何边可以是"折扣"的场景。大多数机器人导航只用非负代价（距离、能量、时间），所以 Dijkstra 和 A* 占主导。

最小生成树（MST）

对一个连通、无向、带权的图，MST 是连接全部顶点且总权重最小的那 V − 1 条边的子集。两种经典算法，都是 O(E log V)：

• Kruskal 算法： 把所有边按权重升序排序；贪心地逐条加入，只要它不形成环。环的检查用一个并查集 / 不相交集合结构（每次查询 O(α(n))，实质上是 O(1)）。
• Prim 算法： 类似 Dijkstra。从任意顶点开始；反复取出那条横跨"树内"到"树外"的最小权边。用以边权为键的优先队列。

何时需要它： 道路/电缆/管道布局、聚类（单链聚类 = 先建一棵 MST 再切掉最大的边）、网络设计。在机器人多智能体协调中，MST 给出一棵连接所有机器人的最小通信树。

表示法的取舍

邻接矩阵与邻接表的区别不只在空间。它们各有最佳适用场景：

• 矩阵： O(V²) 空间，但 O(1) 的边存在性检查。用于稠密图（E ≈ V²），或当你不断追问"u-v 之间有边吗？"时——稠密网格中的物理邻接、全源最短路径（Floyd-Warshall）。
• 表： O(V + E) 空间，但 O(degree) 的边检查。用于稀疏图（道路网络、社交网络、绝大多数现实世界的图）。

大多数生产级图库默认用表。上面的最短路径演示 中的 Graph 结构用的就是以节点 id 为键的邻接表。

数学细节

空间复杂度

Adjacency Matrix: O(V^2)

Adjacency List: O(V + E)

时间复杂度

BFS/DFS: O(V + E)

Check edge (matrix): O(1)

Check edge (list): O(degree)

实现

图的表示

// Adjacency List
let mut graph: Vec<Vec<usize>> = vec![vec![]; n];
graph[0].push(1);  // Edge 0 -> 1
graph[1].push(0);  // Edge 1 -> 0 (undirected)

// BFS from vertex 0
let mut visited = vec![false; n];
let mut queue = VecDeque::from([0]);
while let Some(v) = queue.pop_front() {
    if visited[v] { continue; }
    visited[v] = true;
    for &neighbor in &graph[v] {
        queue.push_back(neighbor);
    }
}

经典算法

• BFS：最短路径（无权图）
• DFS：环检测、拓扑排序
• Dijkstra：最短路径（带权图）
• Kruskal/Prim：最小生成树

练习

三道题目，覆盖最常被问到的三种图惯用法：

• 岛屿数量 —— 中等 · 把网格当作图，洪水填充，连通分量
• 课程表 —— 中等 · 用 Kahn 拓扑排序检测 DAG；每个构建系统背后的算法
• 迷宫中的最短路径 —— 中等 · 把 BFS 当作波前扩张；每一个机器人路径规划器的基础

→ 浏览全部练习题