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

3. DFS 核心逻辑

这是算法的灵魂部分。当我们访问一个节点 v 时，将其标记为已访问，然后遍历其所有邻居。如果邻居未被访问，就记录它的前驱是当前节点 v，并递归进入邻居。

private void dfs(int v) {
    visited[v] = true;
    for (int i : G.adj(v)) {
        if (!visited[i]) {
            from[i] = v; // 记录前驱顶点
            dfs(i);
        }
    }
}

注意这里没有显式返回路径，而是通过修改全局的 from 数组隐式记录了路径树。

4. 路径查询与回溯

当我们需要获取从起点到终点 w 的路径时，只需检查 visited[w] 是否为真。如果是，则从 w 开始，顺着 from 数组一直向前跳，直到回到起点（from 值为 -1）。由于我们是逆序收集的，需要使用栈来反转顺序。

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;

    // 构造函数，寻路算法
    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;
    }

    // 打印路径
    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();
    }
}

算法测试与应用

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

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 

算法分析与优化

时间复杂度分析

空间复杂度

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

优化方向

虽然 DFS 能解决连通性问题，但在某些场景下并非最优解：

1. 广度优先搜索 (BFS)：如果需要找最短路径（边数最少），BFS 是更好的选择。
2. 双向搜索：同时从起点和终点开始搜索，可缩小搜索范围。
3. 启发式搜索：如 A*算法，适用于有权图或需要特定导向的场景。

DFS 寻路与 BFS 寻路对比

选择建议：

• 只需要找到任意一条可行路径，或者图非常深时，使用 DFS。
• 必须找到最短路径，或者图比较宽时，使用 BFS。

实际应用场景

DFS 寻路在实际开发中有着广泛的应用：

1. 迷宫求解
2. 网络路由协议中的路径发现
3. 社交网络中查找关系链
4. 游戏中的 AI 路径规划（非最优路径）
5. 依赖关系解析（如 Maven 依赖树）

总结

本文详细拆解了基于 DFS 的图寻路算法。通过 Java 代码展示了如何维护访问状态和前驱记录，实现了从起点到终点的路径回溯。虽然 DFS 不能保证找到最短路径，但其实现简单、逻辑清晰，是理解更复杂图算法（如 Dijkstra、A*）的重要基石。掌握这一算法有助于在处理图结构数据时快速定位连通性。