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

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

一、寻路算法概述

图的寻路算法是图论中的基础算法之一，用于找到从一个顶点到另一个顶点的路径。深度优先搜索 (DFS) 是实现寻路算法的一种有效方法，它沿着图的深度方向尽可能远地搜索路径。

DFS 寻路示例

假设有一个图，从顶点 0 到顶点 6 的 DFS 路径可能是：0 → 1 → 4 → 6。

二、算法核心思想

1. 记录路径：使用 from 数组记录每个顶点的前驱顶点。
2. 深度优先遍历：从起点开始递归访问所有未访问的邻接顶点。
3. 路径回溯：通过 from 数组逆向回溯找到完整路径。

数据结构设计

• G：图的引用
• s：起始顶点
• visited：布尔数组，记录顶点是否被访问过
• from：整型数组，记录路径中每个顶点的前驱顶点
• 方法：dfs(int v), hasPath(int w), path(int w), showPath(int w)

三、算法实现详解

1. 核心数据结构

• visited 数组：记录顶点是否被访问过
• from 数组：记录路径中每个顶点的前驱顶点
• s：起始顶点

2. 构造函数初始化

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

3. DFS 实现

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

4. 路径查询方法

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

六、算法分析与优化

时间复杂度分析

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

空间复杂度

• O(V) 用于存储 visited 和 from 数组

优化方向

1. 广度优先搜索 (BFS)：可以找到最短路径
2. 双向搜索：同时从起点和终点开始搜索
3. 启发式搜索：如 A* 算法，适用于有权图

七、DFS 寻路与 BFS 寻路对比

特性	DFS	BFS
数据结构	栈/递归	队列
路径性质	不一定是最短路径	保证最短路径

选择建议：

• 需要找到任意路径时使用 DFS
• 需要找到最短路径时使用 BFS
• 图非常大时 DFS 内存消耗更少

八、实际应用场景

1. 迷宫求解
2. 网络路由
3. 社交网络中查找关系链
4. 游戏中的 AI 路径规划
5. 依赖关系解析

九、总结

本文详细介绍了基于 DFS 的图寻路算法，重点讲解了：

1. 算法核心思想和数据结构设计
2. 完整的 Java 实现代码
3. 算法的时间复杂度和空间复杂度分析
4. 与 BFS 寻路的对比
5. 实际应用场景

DFS 寻路算法是图算法的基础，虽然不能保证找到最短路径，但实现简单且在某些场景下效率很高。理解这一算法有助于学习更复杂的图算法如 Dijkstra、A* 等。