python - 广度优先搜索中的孤立顶点错误

Question

我从这里找到了 bfs_visited 的实现(返回广度优先搜索算法已到达的所有节点): http://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/

def bfs(graph, start):
    visited, queue = set(), [start]
    while queue:
        vertex = queue.pop(0)
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(graph[vertex] - visited)
    return visited

bfs(graph, 'A') # {'B', 'C', 'A', 'F', 'D', 'E'}

它与图表的这种表示形式配合得很好:

graph1 = {'A': set(['B', 'C']),
     'B': set(['A', 'D', 'E']),
     'C': set(['A', 'F']),
     'D': set(['B']),
     'E': set(['B', 'F']),
     'F': set(['C', 'E'])}

但我想改用这个实现:

graph2 = { 1: set([2]),                    # changed
    2: set([1, 3, 4]),
    3: set([2, 4]),
    4: set([2, 3]),
    5: set([]),
            6: set([5])}

这几乎可以正常工作:

>>> bfs_visited(graph2, graph2[1])
set([1, 2, 3, 4])

除了在孤立顶点的情况下，它返回一个空集，而不是 包含单个元素的集合:

>>> bfs_visited(graph2, graph2[5])
set([])

有没有办法在上述情况下使用第二种表示形式将 set([5]) 作为输出？

Answer 1

首先，你不一致，要么在键和值中都使用字符串，要么使用整数，不要混合使用它们

graph2 = { '1': set(['2']),
           '2': set(['1', '3', '4']),
           '3': set(['2', '4']),
           '4': set(['2', '3', '6']),
           '5': set([]),
           '6': set(['4'])}

第二，你的 bfs 接受顶点名称，而不是它们的邻域，所以你应该调用

bfs(graph2, '5') #correct

不是

bfs(graph2, graph2['5']) #incorrect

它就像一个魅力

>>> bfs(graph2, '2') 
set(['1', '3', '2', '4', '6'])
>>> bfs(graph2, '5') 
set(['5'])