图论寻路算法：深度优先搜索 (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，而不会选择更长的路径（如果存在的话）。

四、算法分析与优化

时间复杂度

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

空间复杂度

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

优化方向

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

五、DFS 与 BFS 对比

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

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

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

六、总结

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