Java实现图深度优先搜索与路径查找算法详解

路径查找的实际意义

在现实应用中，例如地图导航系统输入出发地与目的地，系统需规划出一条可通行的路线。这类需求映射为计算机科学中的经典图论问题：给定无向图 G 的起点 s 和终点 v，如何判定是否存在一条连接两点的边序列？若存在，请将其完整输出。

如图所示，寻找从顶点 0 到达顶点 4 的路径。图中红色标识的连接方式即为有效路径，其顶点序列表示为 0-2-3-4。

算法核心原理：深度优先搜索

要实现路径查找，必须对图进行系统性遍历。我们选择基于深度优先搜索（Depth-First Search, DFS）来实现该功能，其基本逻辑是尽可能深地搜索树的分支。

与普通 DFS 仅标记是否访问过不同，我们需要额外维护一个整数数组 edgeTo[]。该数组用于记录从起点 s 到达当前顶点时，上一步所在的顶点编号。当递归回溯或终止时，我们可以顺着 edgeTo 倒推，从而重建整条路径。

假设设定起点 s 为 0，搜索过程如下：

工作原理总结：
edgeTo 数组的下标代表目标顶点，存储的值代表该顶点在到达前经过的最后一个顶点（即父节点）。一旦搜索完成，查询从起点 0 到任意顶点 v 的路径变得非常直观。

类设计与实现步骤

第1步：确定 API 设计

在设计类之前，明确需要管理的成员变量及对外提供的操作方法：

第2步：编写路径查找核心代码

以下是完整的 DepthFirstPaths Java 实现。代码包含详细的注释，展示了数组初始化、递归遍历以及路径还原的逻辑：

/**
 * 图的路径查找类 (基于深度优先搜索)
 */
public class DepthFirstPaths {
    // 索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean[] marked;
    // 记录起点
    private int s;
    // 索引代表顶点，值代表从起点s到当前顶点路径上的上一个顶点
    private int[] edgeTo;

    /**
     * 构造深度优先搜索对象
     * @param G 图对象
     * @param s 起点顶点编号
     */
    public DepthFirstPaths(Graph G, int s){
        // 根据图的顶点总数初始化标记数组
        this.marked = new boolean[G.V()];
        // 记录起点
        this.s = s;
        // 初始化路径追踪数组
        this.edgeTo = new int[G.V()];

        // 执行深度优先搜索填充数据
        dfs(G, s);
    }

    /**
     * 使用深度优先搜索找出G图中v顶点的所有相邻顶点
     */
    private void dfs(Graph G, int v){
        // 标记当前顶点v为已搜索
        marked[v] = true;

        // 遍历顶点v的邻接表，获取每一个相邻的顶点w，继续递归
        for (Integer w : G.adj(v)) {
            // 如果顶点w尚未被搜索过，则确立路径关系并深入搜索
            if (!marked[w]){
                // 记录：到达顶点w的前一个节点是v
                edgeTo[w] = v;
                dfs(G, w);
            }
        }
    }

    /**
     * 判断顶点w与起点s之间是否存在路径
     */
    public boolean hasPathTo(int v){
        return marked[v];
    }

    /**
     * 找出从起点s到顶点v的路径
     * @return 路径上的顶点栈，若无路径则返回null
     */
    public Stack<Integer> pathTo(int v){
        // 如果不可达，直接返回空
        if (!hasPathTo(v)){
            return null;
        }

        // 创建栈对象，用于逆向收集路径中的所有顶点
        Stack<Integer> path = new Stack<>();

        // 利用edgeTo数组，从顶点v开始向前回溯，直到回到起点s
        for (int x = v; x != s; x = edgeTo[x]){
            path.push(x);
        }

        // 将起点也压入栈底
        path.push(s);

        // 此时栈顶是起点，出栈顺序即为从起点到终点的路径
        return path;
    }
}