图寻路算法用于寻找图中两点间的路径。深度优先搜索 (DFS) 通过递归遍历邻接顶点记录路径前驱，实现简单但未必最短。本文介绍基于 Java 的 DFS 寻路类 Path，包含数据结构设计、初始化、核心遍历及路径回溯方法。代码展示了如何构建图、执行 DFS 并输出路径结果。分析了时间复杂度 O(V+E) 和空间复杂度 O(V)，并与广度优先搜索 (BFS) 对比，指出 DFS 适用于任意路径查找，而 BFS 保证最短路径。应用场景涵盖迷宫求解、网络路由及游戏 AI 规划等。
图的寻路算法是图论中的基础算法之一，用于找到从一个顶点到另一个顶点的路径。深度优先搜索 (DFS) 是实现寻路算法的一种有效方法，它沿着图的深度方向尽可能远地搜索路径。
假设有一个图，从顶点 0 到顶点 6 的 DFS 路径可能是：0 → 1 → 4 → 6。
from 数组记录每个顶点的前驱顶点。from 数组逆向回溯找到完整路径。G：图的引用s：起始顶点visited：布尔数组，记录顶点是否被访问过from：整型数组，记录路径中每个顶点的前驱顶点dfs(int v), hasPath(int w), path(int w), showPath(int w)visited 数组：记录顶点是否被访问过from 数组：记录路径中每个顶点的前驱顶点s：起始顶点public Path(Graph graph, int s) {
G = graph;
assert s >= 0 && s < G.V();
visited = new boolean[G.V()];
from = new int[G.V()];
for (int i = 0; i < G.V(); i++) {
visited[i] = false;
from[i] = -1;
}
this.s = s;
dfs(s);
}
private void dfs(int v) {
visited[v] = true;
for (int i : G.adj(v)) {
if (!visited[i]) {
from[i] = v; // 记录前驱顶点
dfs(i);
}
}
}
boolean hasPath(int w) {
assert w >= 0 && w < G.V();
return visited[w];
}
Vector<Integer> path(int w) {
assert hasPath(w);
Stack<Integer> stack = new Stack<>();
int p = w;
while (p != -1) {
stack.push(p);
p = from[p];
}
Vector<Integer> res = new Vector<>();
while (!stack.empty()) res.add(stack.pop());
return res;
}
import java.util.Stack;
import java.util.Vector;
/**
* 基于 DFS 的寻路算法
*/
public class Path {
private Graph G; // 图的引用
private int s; // 起始点
private boolean[] visited; // 记录访问过的节点
private int[] from; // 记录路径，from[i] 表示 i 的前驱节点
// 构造函数，寻路算法
public Path(Graph graph, int s) {
G = graph;
assert s >= 0 && s < G.V();
visited = new boolean[G.V()];
from = new int[G.V()];
for (int i = 0; i < G.V(); i++) {
visited[i] = false;
from[i] = -1;
}
this.s = s;
// 开始 DFS 寻路
dfs(s);
}
// 深度优先遍历
private void dfs(int v) {
visited[v] = true;
for (int i : G.adj(v)) {
if (!visited[i]) {
from[i] = v;
dfs(i);
}
}
}
// 判断是否有路径
boolean {
w >= && w < G.V();
visited[w];
}
Vector<Integer> {
;
Stack<Integer> stack = <>();
w;
(p != -) {
stack.push(p);
p = from[p];
}
Vector<Integer> res = <>();
(!stack.empty()) res.add(stack.pop());
res;
}
{
;
Vector<Integer> vec = path(w);
( ; i < vec.size(); i++) {
System.out.print(vec.elementAt(i));
(i != vec.size() - )
System.out.print();
}
System.out.println();
}
}
public class PathTest {
public static void main(String[] args) {
// 创建一个图
Graph g = new SparseGraph(7, false);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 5);
g.addEdge(4, 6);
// 寻路算法测试
Path path = new Path(g, 0);
System.out.println("Path from 0 to 6:");
path.showPath(6); // 输出：0 -> 1 -> 4 -> 6
System.out.println("Path from 0 to 5:");
path.showPath(5); // 输出：0 -> 2 -> 5
System.out.println("Has path to 3: " + path.hasPath(3));
System.out.println("Has path to 6: " + path.hasPath(6));
}
}
Path from 0 to 6: 0 -> 1 -> 4 -> 6
Path from 0 to 5: 0 -> 2 -> 5
Has path to 3: true
Has path to 6: true
| 操作 | 时间复杂度 |
|---|---|
| 初始化 | O(V) |
| DFS 遍历 | O(V + E) |
| 路径查询 | O(L) L 为路径长度 |
| 特性 | DFS | BFS |
|---|---|---|
| 数据结构 | 栈/递归 | 队列 |
| 路径性质 | 不一定是最短路径 | 保证最短路径 |
选择建议：
本文详细介绍了基于 DFS 的图寻路算法，重点讲解了：
DFS 寻路算法是图算法的基础，虽然不能保证找到最短路径，但实现简单且在某些场景下效率很高。理解这一算法有助于学习更复杂的图算法如 Dijkstra、A* 等。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online