如何修改基于邻接矩阵的DFS算法以查找指定终点的路径？

嘿，这个需求我之前做过好多次！要把普通的全量DFS改成定向找v到d的路径，核心就是在遍历中实时追踪路径，一旦碰到目标就立刻终止搜索，不用再浪费时间遍历其他无关分支。下面我一步步给你拆解怎么改：

核心修改要点 #

普通DFS只负责标记所有可达节点，我们需要给它加三个关键功能：

• 维护一个当前路径列表，记录走到当前节点的完整路径
• 每访问一个节点就检查是不是目标d，是的话直接返回路径
• 走不通的分支要回溯，把当前节点从路径里移除，避免路径包含无效节点

修改后的伪代码实现 #

function DFS(G, v, d):
    # 初始化：visited数组标记已访问节点，path记录当前路径
    visited = array of size N, all set to false
    path = empty list

    # 定义递归辅助函数，负责实际遍历逻辑
    function dfsHelper(currentNode):
        # 标记当前节点为已访问，避免重复遍历（防止环）
        visited[currentNode] = true
        # 把当前节点加入路径
        path.append(currentNode)

        # 关键：检查是否到达目标节点
        if currentNode == d:
            return true  # 返回成功信号，触发路径传递

        # 遍历当前节点的所有邻居（邻接矩阵中G[currentNode][u] == 1表示u是邻居）
        for each u from 0 to N-1:
            if G[currentNode][u] == 1 and not visited[u]:
                # 递归访问邻居，如果递归返回true（找到目标），直接向上传递成功信号
                if dfsHelper(u):
                    return true

        # 走到这里说明当前节点的所有分支都找不到目标，回溯：移除当前节点
        path.pop()
        return false

    # 启动递归，从源节点v开始
    if dfsHelper(v):
        return path  # 找到路径，返回完整路径列表
    else:
        return null  # 不存在从v到d的路径

关键细节解释 #

1. 回溯机制：当某个节点的所有邻居都遍历完还没找到目标时，path.pop()会把这个节点从路径中移除，保证最终返回的路径是从v到d的唯一有效路径，不会包含走不通的分支。
2. 提前终止：一旦递归找到目标，就通过return true立刻终止后续遍历，不用再处理其他邻居，大大提升效率。
3. 环的处理：visited数组是必须的，避免图中有环时出现无限递归的情况。

额外说明 #

如果你的图是有向图，这个逻辑完全适用；如果是无向图，邻接矩阵是对称的，也一样能正常工作。要是你需要输出所有可能的路径，只需要去掉提前终止的逻辑，找到目标时记录路径然后继续遍历就行，但你的需求是判断存在性并输出路径，上面的代码刚好匹配。

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