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

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

• • 一、寻路算法概述
  • • DFS寻路示例
  • 二、算法核心思想
  • • 数据结构设计
  • 三、算法实现详解
  • • 1. 核心数据结构
      • 2. 构造函数初始化
      • 3. DFS实现
      • 4. 路径查询方法
  • 四、完整代码实现
  • 五、算法测试与应用
  • • 测试代码
      • 输出结果
  • 六、算法分析与优化
  • • 时间复杂度分析
      • 空间复杂度
      • 优化方向
  • 七、DFS寻路与BFS寻路对比
  • 八、实际应用场景
  • 九、总结

一、寻路算法概述

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

DFS寻路示例

0

1

2

3

4

5

6

从顶点0到顶点6的DFS路径可能是：0 → 1 → 4 → 6

二、算法核心思想

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

数据结构设计

Path

-Graph G

-int s

-boolean[] visited

-int[] from

+dfs(int v)

+hasPath(int w)

+path(int w)

+showPath(int w)

三、算法实现详解

1. 核心数据结构

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

2. 构造函数初始化

1public Path(Graph graph, int s) {
2    G = graph;
3    assert s >= 0 && s < G.V();
4    visited = new boolean[G.V()];
5    from = new int[G.V()];
6    for(int i = 0; i < G.V(); i++) {
7        visited[i] = false;
8        from[i] = -1;
9    }
10    this.s = s;
11    dfs(s);
12}
13

3. DFS实现

1private void dfs(int v) {
2    visited[v] = true;
3    for(int i : G.adj(v)) {
4        if(!visited[i]) {
5            from[i] = v;  // 记录前驱顶点
6            dfs(i);
7        }
8    }
9}
10

4. 路径查询方法

1boolean hasPath(int w) {
2    assert w >= 0 && w < G.V();
3    return visited[w];
4}
5
6Vector<Integer> path(int w) {
7    assert hasPath(w);
8    
9    Stack<Integer> s = new Stack<>();
10    int p = w;
11    while(p != -1) {
12        s.push(p);
13        p = from[p];
14    }
15    
16    Vector<Integer> res = new Vector<>();
17    while(!s.empty())
18        res.add(s.pop());
19    
20    return res;
21}
22

四、完整代码实现

1
2import java.util.Stack;
3import java.util.Vector;
4
5/**
6 * 基于DFS的寻路算法
7 */
8public class Path {
9    private Graph G;       // 图的引用
10    private int s;        // 起始点
11    private boolean[] visited;  // 记录访问过的节点
12    private int[] from;   // 记录路径，from[i]表示i的前驱节点
13
14    // 构造函数，寻路算法
15    public Path(Graph graph, int s) {
16        G = graph;
17        assert s >= 0 && s < G.V();
18        
19        visited = new boolean[G.V()];
20        from = new int[G.V()];
21        for(int i = 0; i < G.V(); i++) {
22            visited[i] = false;
23            from[i] = -1;
24        }
25        this.s = s;
26        
27        // 开始DFS寻路
28        dfs(s);
29    }
30
31    // 深度优先遍历
32    private void dfs(int v) {
33        visited[v] = true;
34        for(int i : G.adj(v)) {
35            if(!visited[i]) {
36                from[i] = v;
37                dfs(i);
38            }
39        }
40    }
41
42    // 判断是否有路径
43    boolean hasPath(int w) {
44        assert w >= 0 && w < G.V();
45        return visited[w];
46    }
47
48    // 获取路径
49    Vector<Integer> path(int w) {
50        assert hasPath(w);
51        
52        Stack<Integer> stack = new Stack<>();
53        int p = w;
54        while(p != -1) {
55            stack.push(p);
56            p = from[p];
57        }
58        
59        Vector<Integer> res = new Vector<>();
60        while(!stack.empty())
61            res.add(stack.pop());
62        
63        return res;
64    }
65
66    // 打印路径
67    void showPath(int w) {
68        assert hasPath(w);
69        
70        Vector<Integer> vec = path(w);
71        for(int i = 0; i < vec.size(); i++) {
72            System.out.print(vec.elementAt(i));
73            if(i != vec.size() - 1)
74                System.out.print(" -> ");
75        }
76        System.out.println();
77    }
78}
79

五、算法测试与应用

测试代码

1public class PathTest {
2    public static void main(String[] args) {
3        // 创建一个图
4        Graph g = new SparseGraph(7, false);
5        g.addEdge(0, 1);
6        g.addEdge(0, 2);
7        g.addEdge(1, 3);
8        g.addEdge(1, 4);
9        g.addEdge(2, 5);
10        g.addEdge(4, 6);
11        
12        // 寻路算法测试
13        Path path = new Path(g, 0);
14        
15        System.out.println("Path from 0 to 6:");
16        path.showPath(6);  // 输出：0 -> 1 -> 4 -> 6
17        
18        System.out.println("Path from 0 to 5:");
19        path.showPath(5);  // 输出：0 -> 2 -> 5
20        
21        System.out.println("Has path to 3: " + path.hasPath(3));
22        System.out.println("Has path to 6: " + path.hasPath(6));
23    }
24}
25

输出结果

1Path from 0 to 6:
20 -> 1 -> 4 -> 6
3Path from 0 to 5:
40 -> 2 -> 5
5Has path to 3: true
6Has path to 6: true
7

六、算法分析与优化

时间复杂度分析

空间复杂度

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

优化方向

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

七、DFS寻路与BFS寻路对比

起点

DFS vs BFS

DFS

BFS

使用栈/递归

不一定是最短路径

使用队列

保证最短路径

选择建议：

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

八、实际应用场景

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

九、总结

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

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

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

《图的寻路算法详解：基于深度优先搜索(DFS)的实现》 是转载文章，点击查看原文。