时间戳

首页 > 解决方案 > 深度优先搜索以查找字典中的循环

python - 深度优先搜索以查找字典中的循环

问题描述

我有一个像这样设置的字典

dic3 = {1: 2, 2: 4, 3: 7, 4: 5, 5: 3, 6: 9, 7: 2, 8: None, 9: 8}

我想在指定节点上找到循环（如果有的话）

例如，如果我调用dfs(dic3, 1)它应该返回[2, 4, 5, 3, 7, 2]

但是，我不确定为什么，但我得到了递归堆栈溢出，并且不确定我的错误是什么，即使我可能误解了 DFS 是如何实现的？这是我的代码：

def dfs(g, node):
    seen = []
    if node not in seen:
        seen.append(node)
        for value in g[node]:
            dfs(g, value)
    return seen

标签： python

解决方案

seen是局部变量；当你递归时，函数从头开始。即每次你检查一个新节点时，你的程序就会失忆。传递seen到递归中。

正如评论中所说，发布的代码对于dic3;的给定值没有意义 if nodeis 1, then g[node]is 2, andfor value in 2:是一个错误，因为整数是不可迭代的。您要么需要更改结构dic3以将可迭代作为值，要么需要更改代码以不具有循环。如果我们保持您的给定值dic3，则此方法有效：

def dfs(g, node, seen=None):
    if not seen:
        seen = []
    if node not in seen:
        seen.append(node)
        dfs(g, g[node], seen)
    return seen

dfs(dic3, 1)
# => [1, 2, 4, 5, 3, 7]

使用不同的数据结构：

dic3 = { 1: [2, 3], 2: [4], 3: [4, 1], 4: [] }

你保持循环；但是现在 path 和 seen 会有所不同（当我们访问死胡同时），所以我们仍然需要更改代码结构。由于我们不再需要订单seen，因此我将其更改为 a set，这是一种更有效的结构来完成它需要做的事情：

def dfs(g, node, seen=None):
    if not seen:
        seen = set()
    if node in seen:
        return []
    seen.add(node)
    for value in g[node]:
        path_forward = dfs(g, value, seen)
        if path_forward is not None:
            return [node] + path_forward

dfs(dic3, 1)
# => [1, 3]
dfs(dic3, 2)
# => None

推荐阅读