图论寻路算法：深度优先搜索 (DFS) 实现

图论寻路算法：深度优先搜索 (DFS) 实现

图的寻路算法是图论中的基础内容，核心目标是在两个顶点之间找到一条连通路径。深度优先搜索（DFS）作为一种经典的遍历策略，能够沿着图的深度方向尽可能远地探索路径。虽然它不能保证找到最短路径，但在许多场景下，其实现简单且效率可观。

一、算法核心思想

要实现基于 DFS 的寻路，关键在于记录访问状态和路径前驱。具体逻辑如下：

1. 记录路径：使用 from 数组保存每个顶点的前驱节点，以便后续回溯。
2. 深度优先遍历：从起点开始，递归访问所有未访问的邻接顶点。
3. 路径回溯：一旦到达终点或完成遍历，通过 from 数组逆向还原完整路径。

数据结构设计

我们需要维护以下几个关键变量：

• visited 数组：标记顶点是否已被访问，防止死循环。
• from 数组：记录路径中每个顶点的前驱顶点索引。
• s：起始顶点的索引。

二、代码实现详解

下面以 Java 为例，展示如何构建一个通用的寻路类 Path。这里假设已经有一个基础的 Graph 接口。

1. 核心数据结构定义

import java.util.Stack;
import java.util.Vector;

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(s); // 立即开始 DFS 遍历
    }

在构造函数中，我们不仅初始化了数组，还直接调用了 dfs(s)。这意味着寻路对象创建时，就已经完成了从起点出发的全图可达性分析。

2. DFS 遍历逻辑

这是算法的核心部分。每当我们访问一个新节点，就将其标记为已访问，并记录它是由哪个节点过来的。

    // 深度优先遍历
    private void dfs(int v) {
        visited[v] = true;
        for (int i : G.adj(v)) {
            if (!visited[i]) {
                from[i] = v; // 记录前驱顶点
                dfs(i);      // 递归访问邻居
            }
        }
    }

注意这里的 from[i] = v。这行代码至关重要，它建立了反向链接。当我们需要查询路径时，只需要从终点不断向前跳，直到回到起点即可。

3. 路径查询与展示

有了 visited 和 from，判断两点是否连通以及获取具体路径就变得很简单。

    // 判断是否有路径
    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 方法中，我们利用栈结构将逆序的前驱链转换为正序的路径输出。这种写法避免了复杂的列表反转操作。

三、测试与应用

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

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，DFS 可能会选择 0 -> 1 -> 4 -> 6，而不会选择更长的路径（如果存在的话）。

四、算法分析与优化

时间复杂度

操作	时间复杂度
初始化	O(V)
DFS 遍历	O(V + E)
路径查询	O(L)，L 为路径长度

其中 V 代表顶点数，E 代表边数。由于每个顶点和每条边最多被访问一次，整体效率较高。

空间复杂度

主要消耗在于 visited 和 from 数组，均为 O(V)。对于大规模图，这通常是可接受的开销。

优化方向

1. 广度优先搜索 (BFS)：如果需要最短路径，应改用 BFS。
2. 双向搜索：同时从起点和终点开始搜索，减少搜索空间。
3. 启发式搜索：如 A*算法，适用于有权图或需要特定导向的场景。

五、DFS 与 BFS 对比

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

• DFS：使用栈或递归，不保证最短路径，但内存占用相对较小，适合寻找任意路径。
• BFS：使用队列，保证找到最短路径（无权图），但内存消耗随层级增加。

建议：迷宫求解、依赖关系解析等对路径长度不敏感的场景，DFS 往往足够；而在网络路由、社交关系最短链路查找中，BFS 更为合适。

六、总结

深度优先搜索是图算法的基石之一。通过简单的 from 数组回溯机制，我们就能轻松实现路径查找功能。虽然它无法像 Dijkstra 或 A*那样处理加权图的最短路径问题，但其实现的简洁性和通用性使其成为学习更复杂算法前的最佳入门实践。掌握这一算法，有助于进一步理解图论中的连通性、拓扑排序等高级概念。