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

2. DFS 递归实现

这是算法的核心部分。当我们访问一个节点 v 时，将其标记为已访问，然后遍历它的所有邻接点。如果邻接点未被访问，就记录前驱并继续深入。

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

3. 路径查询方法

遍历结束后，我们可以通过 hasPath 快速判断两点是否连通。如果需要获取具体路径，则利用 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();
    }
}

测试与验证

为了验证算法的正确性，我们可以构建一个简单的无向图进行测试。注意这里使用了 SparseGraph 作为图的实现，实际项目中请确保该类已正确定义。

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

DFS 与 BFS 对比

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

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

选择建议：

• 若只需确认连通性或寻找任意路径，DFS 更轻量。
• 若必须保证步数最少（如地图导航），请使用 BFS。

应用场景与总结

DFS 寻路算法虽然简单，但在很多领域都有广泛应用，例如：

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

总的来说，理解 DFS 是实现更复杂图算法（如 Dijkstra、A*）的基础。它不保证最短路径，但在特定场景下效率极高且易于实现。掌握这一算法有助于构建更健壮的系统架构。