外观
17 - 图的 DFS 与 BFS:依赖关系、社交网络与最短跳数
摘要
从一个服务出发,能调用到哪些服务?两名用户之间,最少经过几层好友关系?这类问题可以把对象表示为节点,把关系表示为边,再沿边搜索。关系网络可能共享节点或形成环,因此不能直接照搬不带访问标记的树遍历。
本文先解释图的表示,再比较深度优先搜索(DFS)与广度优先搜索(BFS),说明如何避免重复访问,以及为什么 BFS 能在无权图中求最短跳数。
1. 图的表示
图由节点和边组成。路径是沿边依次经过的一串节点;沿边走一圈又回到起点,就形成了环。下文用 V 表示节点数、E 表示边数,并把节点编号为 0 到 n - 1。
邻接表为每个节点保存一份相邻节点列表。graph.get(u) 表示从 u 沿一条边可以到达的节点,遍历它就能找到下一步可走的位置。
另一种表示是邻接矩阵,用一个 V × V 的表记录每对节点是否有边。查询两点是否直接相连是 O(1),但空间为 O(V²)。邻接表空间通常为 O(V+E),只保存已有的边,更适合边数远少于节点对数的稀疏图。下面是建图片段,需要放入类和方法中,并导入 java.util 中的集合类。
java
List<List<Integer>> graph = new ArrayList<>(n);
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
graph.get(from).add(to);上面的语句添加有向边 from -> to。有向边只能沿指定方向走;无向边允许两边互相到达,因此需要再执行 graph.get(to).add(from),在两个方向各添加一次。
有向图不能自动补反向边。建图前必须明确边的业务含义:服务调用中的 A -> B 可以表示 A 调用 B;后续拓扑排序文章则用 A -> B 表示 B 依赖 A。文字中的“依赖”可能采用不同口径,方向建反就会改变可达性、依赖顺序和路径结果。
2. DFS
**DFS(Depth-First Search,深度优先搜索)**先沿一个未访问的邻居继续深入,直到没有新节点可走,再退回上一层尝试其他邻居。递归调用栈保存了“从哪里进入、回来后继续处理哪里”的状态。
图中同一节点可能经不同路径到达。visited[node] 表示该节点已经发现;进入节点时先标记,再搜索邻居,才能防止环使递归反复回到旧节点。下面是方法片段,要求 visited 的长度与节点数一致,初始值全部为 false,节点编号合法。
java
static void dfs(int node, List<List<Integer>> graph, boolean[] visited) {
if (visited[node]) return;
visited[node] = true;
for (int next : graph.get(node)) {
dfs(next, graph, visited);
}
}一次调用只访问起点能够到达的节点。DFS 的访问顺序取决于邻接表中的排列,不保证先找到最短路径。若图是一条很长的链,递归调用也会很深,可能导致调用栈溢出;深度不可控时可用自己维护的栈,即显式栈,替代递归。
DFS 也可以作为路径枚举、环检测和拓扑相关算法的基础,但需要增加相应状态。上面的全局 visited 只做去重遍历,不会枚举所有路径。
对有向图检测环通常需要三种颜色,也就是三种状态:未访问、当前递归路径中、已经完成。若一条边指向当前递归路径中的祖先,这条回边会与已有路径闭合成环;指向已完成节点则不一定有环。普通布尔型 visited 无法区分这两种情况,不能单凭“邻居已访问”判断有向环。
3. BFS 与最短跳数
**BFS(Breadth-First Search,广度优先搜索)**使用先进先出的队列:先处理起点,再处理与起点相隔一条边的节点,然后是相隔两条边的节点。每跨过一条边算一跳,最短跳数就是所有可行路径中最少的边数。
下面的方法用 distance 同时保存访问状态和距离:-1 表示尚未发现,起点的距离为 0。发现邻居时把它的距离设为当前距离加 1,再入队。输入要求起点、终点和邻接表中的编号都合法;返回 -1 表示目标不可达,起点等于终点时返回 0。
java
static int shortestHops(int start, int target, List<List<Integer>> graph) {
int[] distance = new int[graph.size()];
java.util.Arrays.fill(distance, -1);
var queue = new java.util.ArrayDeque<Integer>();
queue.offer(start);
distance[start] = 0; // 入队时立即标记
while (!queue.isEmpty()) {
int node = queue.poll();
if (node == target) return distance[node];
for (int next : graph.get(node)) {
if (distance[next] == -1) {
distance[next] = distance[node] + 1;
queue.offer(next);
}
}
}
return -1;
}队列按距离层级处理节点。距离为 d 的节点发现的邻居距离为 d + 1;如果存在更短路径,其上一层节点就会更早被处理,所以目标不可能先由更长路径发现。因此,在无权图中,BFS 首次发现节点时的层数就是最短边数。
这里的无权指每条边只计一跳,不比较费用或耗时。假设一条边的耗时大于另一条路径上两条边的总耗时,少一跳就不代表耗时更低。边权不同时,不能直接用这个 BFS 求最低成本。
4. 为什么入队时标记
假设起点先发现 A、B,而 A、B 都能到达 C。处理 A 时 C 入队;若此时还不标记,处理 B 时会认为 C 尚未发现,再把 C 加入队列。入队时标记表示“已经安排处理”,不必等到真正处理它才去重。
这样每个节点最多入队一次,也能固定它首次发现时的距离和前驱。若延迟到出队才标记,同一节点可能被多个前驱重复入队,造成冗余和队列膨胀。
5. 多源 BFS
多源 BFS从多个起点共同向外搜索:在搜索开始前,把所有源点的距离设为 0 并标记、入队,然后使用同一个队列继续 BFS。各源点的第 1 层会先于第 2 层处理,因此节点首次发现时得到的是所有源点中最少的跳数。
例如,在无权、无向网络中求到最近机房的跳数,或在按允许移动方向建图的矩阵中求最近故障点。对有向图,沿原边搜索得到的是“最近源点到该节点”的距离;如果要计算“该节点到最近源点”,应在反向图上搜索。
所有源点必须在这次搜索开始前一起入队。依次从每个源点单独 BFS 也能求出各自的距离,再逐节点取最小值,但会重复工作;若直接覆盖已有结果或混用访问标记,则可能因处理顺序得到错误结果。
6. 完整可运行示例:DFS、BFS 与路径恢复
下面的完整类对应文件名 GraphTraversalDemo.java,使用 java.util 集合,无外部依赖。代码包含局部变量 var,按语法要求需使用 Java 10 或更高版本;前面的建图和方法代码是局部片段。
graph 构造无向图。输入要求 n >= 0、每条边包含两个合法编号,且搜索起点与目标存在;空图没有合法起点。代码没有额外参数校验。完整示例的 dfs 要求入口尚未访问,与第 2 节在入口直接检查 visited 的写法不同。
要恢复路径,还需保存前驱(predecessor),即首次发现某节点时从哪个节点走来。prev[v] = u 记录这条关系;找到目标后沿前驱回到起点,再反转列表。目标不可达时返回空列表,起点等于目标时返回只含起点的列表。多条最短路径并存时,邻接表顺序决定返回哪一条。
java
import java.util.*;
/**
* 可运行示例:图的 DFS 与 BFS:依赖关系、社交网络与最短跳数。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class GraphTraversalDemo {
static List<List<Integer>> graph(int n, int[][] edges) {
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
for (int[] e : edges) {
g.get(e[0]).add(e[1]);
g.get(e[1]).add(e[0]);
}
return g;
}
static void dfs(
int u,
List<List<Integer>> g,
boolean[] seen,
List<Integer> out
) {
// 进入节点时立即标记,防止环导致重复递归。
seen[u] = true;
out.add(u);
for (int v : g.get(u)) if (!seen[v]) dfs(v, g, seen, out);
}
static List<Integer> shortestPath(int s, int target, List<List<Integer>> g) {
int[] prev = new int[g.size()];
Arrays.fill(prev, -1);
boolean[] seen = new boolean[g.size()];
Deque<Integer> q = new ArrayDeque<>();
q.offer(s);
// 入队时标记;若延迟到出队,同一节点可能被重复加入队列。
seen[s] = true;
while (!q.isEmpty()) {
int u = q.poll();
if (u == target) break;
for (int v : g.get(u))
if (!seen[v]) {
seen[v] = true;
// 首次到达 v 的边数最少,保存前驱用于恢复路径。
prev[v] = u;
q.offer(v);
}
}
if (!seen[target]) return List.of();
List<Integer> path = new ArrayList<>();
// 从终点沿前驱回溯到源点,再反转成正向路径。
for (int at = target; at != -1; at = prev[at]) path.add(at);
Collections.reverse(path);
return path;
}
// 运行入口:使用一组包含典型边界的数据验证主要算法。
public static void main(String[] args) {
var g = graph(6, new int[][] {
{ 0, 1 },
{ 1, 2 },
{ 0, 3 },
{ 3, 4 },
{ 4, 5 },
});
List<Integer> order = new ArrayList<>();
dfs(0, g, new boolean[6], order);
System.out.println(order);
System.out.println(shortestPath(0, 5, g));
}
}BFS 分层推演
图中存在 0-1-2 和 0-3-4-5。从 0 出发,第一层发现 1、3,第二层发现 2、4,第三层发现 5。prev[5] = 4、prev[4] = 3、prev[3] = 0,沿前驱回溯得到 5、4、3、0,反转后得到路径 [0, 3, 4, 5],共 3 跳。
按现有邻接表顺序,DFS 的预期输出为 [0, 1, 2, 3, 4, 5],路径的预期输出为 [0, 3, 4, 5]。这是手工推演,并非实测。main 只演示这一组连通的无向图,没有覆盖注释所提到的全部边界情况。
在邻接表表示、及时标记的前提下,完整遍历中每个节点、每条邻接记录最多处理常数次,时间为 O(V+E);无向边保存两份记录,不改变这一量级。单一起点只扫描可达部分,BFS 提前找到目标还可提前退出,但这里的距离、访问和前驱数组仍按全部 V 个节点分配或初始化。
不计图本身,两种实现的辅助空间最坏均为 O(V)。DFS 的递归栈取决于最大搜索深度,BFS 的队列取决于搜索前沿,即已经发现、尚未处理的节点集合;此外还要计入访问标记、距离或前驱数组。邻接表本身占 O(V+E) 空间。这些是代码的复杂度分析,不是性能测量。
7. 从连通分量到强连通分量
无向图中的连通分量是一组沿边互相可达、且不能再加入其他可达节点的集合。一次从某节点出发的 DFS/BFS 会遍历它所在的整个分量,但不会自动遍历其他分量。要划分全图,应遍历所有节点:遇到未访问节点就启动一次搜索,共享同一份访问标记;每次新启动的搜索对应一个新分量,孤立节点也单独算一个。
有向图中,“从 A 能到 B”不代表“从 B 能到 A”。组内任意两点都能互相到达、且不能再扩大的集合,称为强连通分量(Strongly Connected Component,SCC)。例如只有 A -> B 时,从 A 能访问到 A、B,但两者并不属于同一个强连通分量。
普通一次 DFS 不能直接划分 SCC,通常使用 Kosaraju、Tarjan 等专门算法。这里先掌握遍历与方向的区别,不能把有向图中一次访问到的节点集合直接当作强连通分量。
8. 验证与排障
- 覆盖有向/无向、自环、重复边、孤立点和多个分量;
- BFS 最短路与小图枚举结果做差分测试,即对相同输入比较两种实现的结果;有多条最短路径时比较边数和路径合法性,不要求节点序列完全相同;
- 记录访问节点数、扫描边数、队列峰值和最大深度;
- 队列异常膨胀时检查是否延迟到出队才标记;
- 递归栈溢出时改显式栈,并确认不是遗漏
visited导致循环。
恢复的路径还应满足:首尾分别为起点和目标,相邻节点间确有对应方向的边。
9. 容易踩的坑
- 图中有环却没有
visited,导致反复进入旧节点。 - 无向边只添加一个方向。
- BFS 用于有不同权重的最短路径。
- 递归 DFS 处理极深图导致栈溢出。
- 只保存
visited,无法知道从哪里走来;需要输出路径时应额外保存前驱。
10. 总结
DFS 沿一条路径深入,BFS 按距离层级扩展;图遍历必须显式处理重复访问。
- 邻接表适合大多数稀疏关系网络。
- BFS 在无权图中保证最短跳数,关键是入队时标记。
- 需要输出路径时,除距离外还要保存前驱关系。