Python

Question

我已经使用递归方法实现了 DFS。但是，我的程序一执行就中断了。

# Non Recursive approach
def Non_Recursive_dfs(graph, source):
    path = []
    stack = []
    stack.append(source)
    
    while stack:
        s = stack.pop()
        if s not in path:
            path.append(s)

        if s in path:
            #leaf node
            continue
        for neighbour in graph[s]:
            stack.append(neighbour)
    
    return " ".join(path)

输入输出：

print(Non_Recursive_dfs(graph, "A"))
O/p: A

谁能解释为什么会这样？

Answer 1

第一个 if 语句保证第二个语句下面的代码将始终执行，因为它会添加 s 到 path 如果它不在其中。您可以简单地将第二个 if 语句更改为 else-if 语句，如下所示：

def Non_Recursive_dfs(graph, source):
    path = []
    stack = []
    stack.append(source)
    
    while stack:
        s = stack.pop()
        if s not in path:
            path.append(s)

        elif s in path:
            #leaf node
            continue
        for neighbour in graph[s]:
            stack.append(neighbour)
    
    return " ".join(path)

我很快为 graph 创建了一些虚拟数据，它似乎运行没问题。

Python - 深度优先搜索非递归方法

Python - Depth First Search Non recursive approach

graph

depth-first-search

data-structures