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

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

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

核心思想与数据结构

DFS 寻路的关键在于记录访问状态和回溯路径。我们需要维护两个核心数组：

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

在实现上，我们通常从起点开始递归访问所有未访问的邻接顶点。当递归返回时，如果当前节点不是起点，则将其前驱关系记录下来。

代码实现细节

下面是一个完整的 Java 实现示例。为了保持逻辑清晰，我们将寻路逻辑封装在 Path 类中，依赖一个基础的 Graph 接口（假设已存在）。

1. 核心类结构

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 的前驱节点

    /**
     * 构造函数，初始化寻路对象
     * @param graph 图实例
     * @param 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 遍历
        dfs(s);
    }

    /**
     * 深度优先遍历核心方法
     * @param v 当前访问的顶点
     */
    private void dfs(int v) {
        visited[v] = true;
        // 遍历邻接点
        for (int i : G.adj(v)) {
            if (!visited[i]) {
                from[i] = v; // 记录前驱，这是回溯的关键
                dfs(i);      // 递归深入
            }
        }
    }

    /**
     * 判断是否存在路径
     * @param w 目标顶点
     * @return 是否存在路径
     */
    boolean hasPath(int w) {
        assert w >= 0 && w < G.V();
        return visited[w];
    }

    /**
     * 获取具体路径
     * @param w 目标顶点
     * @return 路径节点列表
     */
    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;
    }

    /**
     * 打印路径结果
     * @param w 目标顶点
     */
    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();
    }
}

2. 测试与验证

为了验证算法的正确性，我们可以构建一个简单的无向图进行测试。注意，这里假设 SparseGraph 是图中常用的稀疏图实现类。

public class PathTest {
    public static void main(String[] args) {
        // 创建一个包含 7 个顶点的无向图
        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));
    }
}

运行上述代码，控制台将输出具体的路径序列以及连通性判断结果。例如，从顶点 0 到 6 的一条可能路径是 0 -> 1 -> 4 -> 6。

算法分析与优化

复杂度分析

操作	时间复杂度	说明
初始化	O(V)	分配并清空 visited 和 from 数组
DFS 遍历	O(V + E)	每个顶点和边最多访问一次
路径查询	O(L)	L 为路径长度，取决于回溯步数

空间复杂度主要消耗在 visited、from 数组以及递归栈上，总体为 O(V)。

DFS 与 BFS 对比

在实际工程中，选择 DFS 还是 BFS 取决于具体需求：

• DFS：使用栈（或递归），不保证找到最短路径，但内存占用相对较小，适合需要快速找到任意路径的场景。
• BFS：使用队列，天然保证找到无权图中的最短路径，但在大规模图中可能消耗更多内存。

选择建议：

• 若只需确认连通性或寻找任意解，DFS 更高效。
• 若必须要求最短路径（如地图导航），请改用 BFS 或 Dijkstra。

实际应用场景

DFS 寻路算法虽然基础，但在多个领域都有广泛应用：

1. 迷宫求解：尝试所有可能的出口，直到找到通路。
2. 网络路由：检测网络节点间的连通性。
3. 社交网络：查找两人之间的间接关系链。
4. 游戏 AI：简单的 NPC 路径规划或地图探索。
5. 依赖解析：如 Maven 或 Gradle 构建时的依赖树遍历。

总结

本文详细拆解了基于 DFS 的图寻路算法，重点展示了如何通过 from 数组实现路径回溯。尽管 DFS 不能保证最短路径，但其实现简单、逻辑直观，是理解更复杂图算法（如 Dijkstra、A*）的重要基石。掌握这一算法，有助于在处理图结构数据时快速构建解决方案。