图寻路算法详解：基于深度优先搜索 (DFS) 的 Java 实现

图寻路算法详解：基于深度优先搜索 (DFS) 的 Java 实现

图的寻路算法是图论中的基础应用之一，核心目标是在网络中找到从起点到终点的路径。深度优先搜索（DFS）作为一种经典策略，沿着图的深度方向尽可能远地探索，非常适合用于判断连通性或寻找任意一条可行路径。

一、算法核心思想

要实现 DFS 寻路，关键在于记录遍历过程中的状态。我们主要依赖两个数组：

1. visited 数组：标记顶点是否已被访问，防止死循环和重复计算。
2. from 数组：记录路径中每个顶点的前驱节点。一旦找到目标，通过该数组逆向回溯即可还原完整路径。

这种设计使得算法在遍历的同时隐式地构建了路径树，无需额外的复杂结构。

二、数据结构与实现细节

1. 核心类设计

我们需要一个 Path 类来封装寻路逻辑。它持有图的引用，并在初始化时立即执行一次完整的 DFS 遍历，将结果缓存起来供后续查询。

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 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;
    }

    // 打印路径
    void showPath(int w) {
        assert hasPath(w);
        Vector<Integer> vec = path(w);
        for (int i = 0; i < vec.size(); i++) {
            System.out.print(vec.elementAt(i));
            if (i != vec.size() - 1)
                System.out.print(" -> ");
        }
        System.out.println();
    }
}

这里有个细节要注意：path 方法利用栈（Stack）实现了路径的反转。因为 from 数组是从终点向前追溯的，所以入栈顺序是逆序的，出栈后才是正确的路径顺序。

2. 测试代码

为了验证算法的正确性，我们可以构建一个简单的稀疏图进行测试。

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 为路径长度

空间复杂度

主要消耗在于 visited 和 from 数组，均为 O(V)。递归调用栈的深度在最坏情况下也是 O(V)。

优化方向

虽然 DFS 实现简单，但它不能保证找到最短路径。如果业务场景对路径长度敏感，可以考虑以下优化：

1. 广度优先搜索 (BFS)：使用队列代替栈，能保证找到无权图中的最短路径。
2. 双向搜索：同时从起点和终点开始搜索，相遇即停止，减少搜索空间。
3. 启发式搜索：如 A*算法，适用于有权图或需要特定导向的场景。

四、DFS 与 BFS 对比

在实际开发中，选择哪种算法取决于需求：

• 需要任意路径：DFS 足够，且内存占用通常更低。
• 需要最短路径：必须使用 BFS 或 Dijkstra/A*。
• 图非常大：DFS 的递归深度可能成为瓶颈，此时需考虑迭代实现或 BFS。

五、实际应用场景

DFS 寻路不仅仅停留在理论层面，它在很多领域都有落地：

1. 迷宫求解：经典的回溯问题。
2. 网络路由：判断两个节点是否连通。
3. 社交网络：查找两人之间的间接关系链。
4. 游戏 AI：简单的 NPC 寻路逻辑。
5. 依赖解析：如 Maven 或 Gradle 的项目依赖检查。

六、总结

深度优先搜索是图算法的基石。尽管它无法保证最短路径，但其实现简单、逻辑清晰，在处理大规模图的连通性判断时依然高效。掌握 DFS 的实现细节，特别是路径回溯机制，对于理解更复杂的图算法（如 Dijkstra、A*）至关重要。