每个运行的深度优先搜索输出变化

Question

我有下面的深度优先搜索代码：

def dfs(graph, vertex):
    visited = set()
    stack = [vertex]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex])
    return visited

def main():
    test_graph = {
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B', 'F'],
        'F': ['C', 'E']
    }
    print(dfs(test_graph, 'A'))

if __name__ == '__main__':
    main()

每次执行我都会得到不同的输出。

是否可以进行任何更改，使输出始终以 vertex 的值开头（在本例中为 A）？

Answer 1

你的算法很好，它在每个运行上做同样的事情。问题在于使用 set 来 returning 输出。一组未排序，您可能会在不同的运行上得到不同的结果。您可以通过多种方式解决这个问题 - 一种是从集合中创建一个列表，然后在 dfs 函数 return 之前对其进行排序。

另一种解决方案是首先使用列表：

def dfs(graph, vertex):
    visited = []
    stack = [vertex]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.append(vertex)
            stack.extend(graph[vertex])

    return visited

Answer 2

在 Python 中，没有订购 set。您可以使用 collections.OrderedDict 来保持键的插入顺序，同时让 not in 在 O(1) 中工作，就像在集合中一样：

from collections import OrderedDict

def dfs(graph, vertex):
    visited = OrderedDict()
    stack = [vertex]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited[vertex] = True
            stack.extend(graph[vertex])
    return list(visited.keys())

def main():
    test_graph = {
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B', 'F'],
        'F': ['C', 'E']
    }
    print(dfs(test_graph, 'A'))

if __name__ == '__main__':
    main()

每个运行的深度优先搜索输出变化

Depth First Search Output Changes on Every Run

python

graph

depth-first-search

每个 运行 的深度优先搜索输出变化

Depth First Search Output Changes on Every Run

python

graph

depth-first-search

每个运行的深度优先搜索输出变化