Python递归DFS函数到达目标节点未返回的问题求助

嘿，我看到你的问题了——你的DFS递归找到目标节点后还在继续遍历所有节点，这确实是对递归返回机制理解不到位导致的，另外你的代码里还有个容易忽略的小bug，我一起帮你修正。

问题根源 #

1. 递归信号未传递：你当前的代码里，当某个递归分支找到GoalNode时，只是终止了当前这一层递归，但上层的递归函数根本不知道已经找到目标，还会继续遍历当前节点的其他邻居，导致整个DFS停不下来。
2. visited索引错误：你用list(values).index(key)来获取visited的索引，这是错的——visited数组是按MainDictionary的节点顺序初始化的，而values是当前节点的邻接表，它的索引和全局节点的索引完全不对应，会导致visited标记混乱，甚至可能重复访问节点。

解决方案 #

我们需要给递归函数加上返回信号，让找到目标的分支能把“已经找到”的信息传递给所有上层递归，同时修正visited的索引计算：

1. 让DFS函数返回布尔值：找到目标返回True，否则返回False。
2. 每次递归调用后检查返回值，如果是True，立即终止当前层的循环并返回True，让上层也停止。
3. 修正visited的索引：用节点在MainDictionary中的全局索引来标记访问状态。

修改后的完整代码 #

先假设你的MainDictionary示例（方便测试）：

MainDictionary = {
    "F": {"C": 1, "D": 1},
    "C": {},
    "D": {"E": 1},
    "E": {}
}

然后是修正后的函数：

def DFS(visited, StartNode, GoalNode):
    # 获取当前节点在全局字典中的索引，正确标记visited
    node_index = list(MainDictionary).index(StartNode)
    visited[node_index] = True
    print(StartNode)
    
    # 找到目标节点，返回True触发终止信号
    if StartNode == GoalNode:
        return True
    
    adj_nodes = ReturnKeyVal(StartNode)
    for neighbor in adj_nodes:
        # 获取邻居节点的全局索引
        neighbor_index = list(MainDictionary).index(neighbor)
        if not visited[neighbor_index] and adj_nodes[neighbor] != 0:
            # 递归调用后检查是否找到目标，是则立即返回
            if DFS(visited, neighbor, GoalNode):
                return True
    # 当前节点的所有分支都没找到目标，返回False
    return False

def ReturnKeyVal(Target):
    for keys, values in MainDictionary.items():
        if keys == Target:
            return values

visited = [False] * len(MainDictionary)
DFS(visited, "F", "C")

效果说明 #

运行这段代码，输出会是：

F
C

找到C后，递归链会逐层返回，不会再去遍历D和E节点，完美符合你的需求。

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