如何在DFS算法中设置目标节点以到达时终止遍历？

核心解决思路 #

要让DFS找到目标节点就立刻停止，关键是给递归的DFS工具方法加上布尔返回值——用它标记是否已经找到目标。一旦某个递归分支命中目标，就逐层向上返回true，上层循环收到这个信号后，直接停止遍历其他邻接节点，终止整个算法流程。

修改后的代码实现 #

1. 调整DFS工具方法的返回类型 #

把DFSUtil_BUS改成返回boolean，用于传递“是否找到目标”的状态：

private boolean DFSUtil_BUS(int current, int goal, boolean[] visited) {
    // 标记当前节点已访问
    visited[current] = true;

    // 先检查当前节点是否为目标
    if (current == goal) {
        System.err.print(infoLinkedList.get(1).nameStation + ":");
        System.err.print(" |" + goal + "| -> ");
        return true; // 找到目标，返回true终止当前分支
    }

    // 获取当前节点的邻接节点迭代器（替换为你实际的邻接节点获取逻辑）
    Iterator<Integer> i = getAdjacentNodes(current).iterator();
    while (i.hasNext()) {
        int n = i.next();
        if (!visited[n]) {
            // 递归调用，若返回true说明已找到目标，直接向上传递终止信号
            if (DFSUtil_BUS(n, goal, visited)) {
                return true;
            }
        }
    }
    // 当前分支未找到目标，返回false
    return false;
}

2. 调整调用处的逻辑 #

在你原有的循环中，增加对递归返回值的判断，一旦确认找到目标就立刻终止：

Iterator<Integer> i = ...; // 替换为你原来获取迭代器的代码
while (i.hasNext()) {
    int n = i.next();
    if (!visited[n]) {
        // 若递归找到目标，直接终止整个流程
        if (DFSUtil_BUS(n, goal, visited)) {
            return;
        }
    }
}

原代码的问题说明 #

你原来的代码在找到目标时，只是从当前递归层级返回，但上层的循环还会继续遍历其他邻接节点、发起新的递归调用，导致算法不会立即终止。通过让递归方法返回布尔值，上层代码能直接感知到目标已找到，从而停止所有后续操作。

内容的提问来源于stack exchange，提问作者Yara Abd