每次运行的深度优先搜索输出更改

问题描述 投票:1回答:2

我有以下用于深度优先搜索的代码:

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)?

python graph depth-first-search
2个回答
1
投票
您的算法很好,并且每次运行都执行相同的操作。捕获是使用set返回输出。一组没有排序,在不同的运行中可能会得到不同的结果。您可以通过多种方式解决此问题-一种方法是从集合中创建列表并将其排序,然后再从dfs函数返回。

1
投票
在Python中,未排序set。您可以使用collections.OrderedDict来保持键的插入顺序,同时也可以像在集合中那样使collections.OrderedDict在O(1)中工作:
© www.soinside.com 2019 - 2024. All rights reserved.