图结构的层序搜索与最短路径追踪
图的遍历策略主要分为两种：纵向深入探索与横向层级扩展。本文聚焦于后者——基于队列的层序遍历机制，探讨如何高效计算源点到目标节点的最短通路。
核心机制
层序遍历（BFS）依赖队列的先进先出特性，确保节点按距离源点的远近顺序被处理。每访问一个节点，立即将其未访问的邻接节点加入队列尾部，形成逐层向外扩散的搜索模式。
路径回溯原理
与递归式深度搜索不同，层序遍历需显式维护前驱关系。引入prev数组记录每个节点在搜索树中的父节点：
- 初始化时所有元素置为-1，表示无前驱
- 首次发现节点
v时，设置prev[v] = current - 路径重建时从目标节点逆向追溯至源点
完整实现
public class BFSShortestPath {
private final Graph graph;
private final int source;
private final boolean[] marked;
private final int[] prev;
public BFSShortestPath(Graph g, int s) {
this.graph = g;
this.source = s;
int n = g.vertexCount();
this.marked = new boolean[n];
this.prev = new int[n];
Arrays.fill(this.prev, -1);
ArrayDeque<Integer> deque = new ArrayDeque<>();
deque.offer(s);
marked[s] = true;
while (!deque.isEmpty()) {
int cur = deque.poll();
for (int neighbor : g.adjacent(cur)) {
if (!marked[neighbor]) {
deque.offer(neighbor);
marked[neighbor] = true;
prev[neighbor] = cur;
}
}
}
}
public boolean reachable(int v) {
return marked[v];
}
public List<Integer> getPath(int target) {
if (!reachable(target)) return Collections.emptyList();
LinkedList<Integer> path = new LinkedList<>();
for (int x = target; x != -1; x = prev[x]) {
path.addFirst(x);
}
return path;
}
public void displayPath(int target) {
List<Integer> route = getPath(target);
System.out.println(route.stream()
.map(String::valueOf)
.collect(Collectors.joining(" → ")));
}
}关键差异对比
| 特性 | 深度优先 | 广度优先 |
|---|---|---|
| 数据结构 | 调用栈（隐式） | 队列（显式） |
| 路径性质 | 任意通路 | 边数最少的最短路径 |
| 空间复杂度 | O(h)，h为树高 | O(w)，w为最大层宽 |
| 前驱记录 | 递归返回时隐式确定 | 发现时立即写入prev数组 |
验证示例
public static void main(String[] args) {
Graph g = new AdjacencyList(7, false);
loadEdges(g, "graph_data.txt");
BFSShortestPath bfs = new BFSShortestPath(g, 0);
bfs.displayPath(6); // 输出: 0 → 2 → 6
DFSSearch dfs = new DFSSearch(g, 0);
dfs.displayPath(6); // 可能输出: 0 → 1 → 3 → 5 → 6
}当图边权均为单位权重时，BFS首次抵达目标即确定最优解；若边权各异，则需改用Dijkstra等带权最短路径算法。
