广度优先搜索算法

Question

和我之前遇到的问题一样，我正在尝试创建一个广度优先搜索算法，它可以接受一个图并输出顶点访问顺序。它以邻接矩阵（表示图）作为输入，以下是我的进展。

import sys
import Queue

# Input has to be adjacency matrix or list
graphAL2 = {0 : [1,2,3],
        1 : [0,3,4],
        2 : [0,4,5],
        3 : [0,1,5],
        4 : [1,2],
        5 : [2,3] }

# NEED TO FIX:
# - Final graphAL2v print is only displaying key values as 1, not iterating
# through graph and visiting each vertex

def main():
    count = 0
    graphAL2v = {}

    for key, value in graphAL2.items():
        graphAL2v[key] = 0

    print(graphAL2v)

    for key in graphAL2v: # each vertex v in V
        if graphAL2v[key] == 0: # is marked with 0
            bfs(key, count, graphAL2, graphAL2v)
    print(graphAL2v)

def bfs(v, count, graphal, graphv):
    count = count + 1
    print('Visiting', v)

    # Mark v with count and initialize queue with v
    graphv[v] = count
    visited = Queue.Queue()

    while not visited.empty(): #queue not empty:
        print('queue is not empty')
        for element in graphal[v]: # each vertex w in V adjacent to front vertex
            if element == 0:
                count = count + 1
                # mark w with count
                graphal[v] = count
                visited.put()
        visited.get()

if __name__ == '__main__':
    sys.exit(main())

我遇到的问题是我的输出结果

{0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}
('Visiting', 0)
('Visiting', 1)
('Visiting', 2)
('Visiting', 3)
('Visiting', 4)
('Visiting', 5)
{0: 1, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1}

当它遍历“图形”时，对于列表中的所有顶点，将访问顺序显示为1，而不是为每个顶点显示不同的数字。我认为这个错误源于bfs()函数的while循环内部。有没有什么建议可以修复代码，以便我可以实现期望的输出？我也不太熟悉Python中的队列，所以任何帮助都会感激。

- superfluousAM

---

程序不是递归的（或者我错过了吗？） - amit

@amit 你说得对。我不确定为什么我说了递归，显然不是这样的。我的大脑可能已经被整天工作的事情熔化了。 - superfluousAM

显示该问题的最小图是什么？ - Peter Wood

Answer 1

你的代码存在很多问题：

1. 首先，你从未将任何内容放入你创建的队列中，因此它始终为空，你需要将 v 放入队列中，在 while 循环之前，这是起点。

2. 其次，在 for 循环中，你正在检查 element == 0，这是错误的，你需要检查 graphv[element] == 0，也就是该元素是否已经被访问过。

3. 第三，在 for 循环中，你需要设置 graphv[element] = count，表示你访问了 element。

4. 你没有使用 visited.put() 将任何内容放入队列中，你需要将元素作为参数传递给 put() 方法。

5. 在从队列中获取元素时，你需要将其重新赋值给 v，否则 v 永远不会改变，v 表示当前迭代的元素。

示例代码 -

import sys
import Queue

# Input has to be adjacency matrix or list
graphAL2 = {0 : [1,2,3],
        1 : [0,3,4],
        2 : [0,4,5],
        3 : [0,1,5],
        4 : [1,2],
        5 : [2,3] }

# NEED TO FIX:
# - Final graphAL2v print is only displaying key values as 1, not iterating
# through graph and visiting each vertex

def main():
    count = 0
    graphAL2v = {}

    for key, value in graphAL2.items():
        graphAL2v[key] = 0

    print(graphAL2v)

    for key in graphAL2v: # each vertex v in V
        if graphAL2v[key] == 0: # is marked with 0
            bfs(key, count, graphAL2, graphAL2v)
    print(graphAL2v)

def bfs(v, count, graphal, graphv):
    count = count + 1
    print('Visiting', v)

    # Mark v with count and initialize queue with v
    graphv[v] = count
    visited = Queue.Queue()
    visited.put(v)
    while not visited.empty(): #queue not empty:
        print('queue is not empty')
        for element in graphal[v]: # each vertex w in V adjacent to front vertex
            if graphv[element] == 0:
                count = count + 1
                # mark w with count
                graphv[element] = count
                visited.put(element)
        v = visited.get()
    return count

if __name__ == '__main__':
    sys.exit(main())

演示（在上述更改后）-

{0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}
Visiting 0
queue is not empty
queue is not empty
queue is not empty
queue is not empty
queue is not empty
queue is not empty
{0: 1, 1: 2, 2: 3, 3: 4, 4: 5, 5: 6}

- Anand S Kumar

---

这就是答案。更进一步的建议是避免使用Queue.Queue(该模块旨在用于多线程应用程序中的同步)，而是使用collections.deque代替。 - Blckknght

@Anand S Kumar非常感谢您！我总是对比较字典中的元素感到困惑，而您对队列方法的解释让我豁然开朗。我会记住这些方法以备将来遇到类似问题时使用！ - superfluousAM

Answer 2

您可以使用提供搜索算法的图形库之一，如 NetworkX：

from networkx import *
graphAL2 = {0 : [1,2,3],
        1 : [0,3,4],
        2 : [0,4,5],
        3 : [0,1,5],
        4 : [1,2],
        5 : [2,3] }

g = Graph()

# create graph
for node in graphAL2:
    g.add_node(node)
    for target_node in graphAL2[node]:
        g.add_edge(node, target_node)

print bfs_successors(g, 0)

这将获取每个节点的后继节点，导出搜索顺序应该很容易。

输出：

{0: [1, 2, 3], 1: [4], 2: [5]}

- drali