Python 实现广度优先搜索
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/46383493/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Python Implement Breadth-First Search
提问by Anonta
I found an example online, however, returning only the sequence of the BFS elements is not enough for calculation. Let's say the root is the first level of the BFS tree, then its children are second level, etc. How can I know which level are they in, and who is the parent of each node from the code below (I will create an object to store its parent and tree level)?
我在网上找到了一个例子，但是，仅返回 BFS 元素的序列不足以进行计算。假设根是 BFS 树的第一级，然后它的子级是第二级，等等。我怎么知道它们在哪个级别，以及从下面的代码中每个节点的父级是谁（我将创建一个对象存储其父级和树级别）？
# sample graph implemented as a dictionary
graph = {'A': ['B', 'C', 'E'],
'B': ['A','D', 'E'],
'C': ['A', 'F', 'G'],
'D': ['B'],
'E': ['A', 'B','D'],
'F': ['C'],
'G': ['C']}
# visits all the nodes of a graph (connected component) using BFS
def bfs_connected_component(graph, start):
# keep track of all visited nodes
explored = []
# keep track of nodes to be checked
queue = [start]
# keep looping until there are nodes still to be checked
while queue:
# pop shallowest node (first node) from queue
node = queue.pop(0)
if node not in explored:
# add node to list of checked nodes
explored.append(node)
neighbours = graph[node]
# add neighbours of node to queue
for neighbour in neighbours:
queue.append(neighbour)
return explored
bfs_connected_component(graph,'A') # returns ['A', 'B', 'C', 'E', 'D', 'F', 'G']
回答by Anonta
You can keep track of the levels of each node by first assigning level 0 to the start node. Then for each neighbor of node Xassign level level_of_X + 1.
您可以通过首先将级别 0 分配给起始节点来跟踪每个节点的级别。然后为节点X分配级别的每个邻居level_of_X + 1。
Also, your code pushes the same node multiple times into the queue. I used a separate list visitedto avoid that.
此外，您的代码多次将同一个节点推入队列。我使用了一个单独的列表visited来避免这种情况。
# sample graph implemented as a dictionary
graph = {'A': ['B', 'C', 'E'],
'B': ['A','D', 'E'],
'C': ['A', 'F', 'G'],
'D': ['B'],
'E': ['A', 'B','D'],
'F': ['C'],
'G': ['C']}
# visits all the nodes of a graph (connected component) using BFS
def bfs_connected_component(graph, start):
# keep track of all visited nodes
explored = []
# keep track of nodes to be checked
queue = [start]
levels = {} # this dict keeps track of levels
levels[start]= 0 # depth of start node is 0
visited= [start] # to avoid inserting the same node twice into the queue
# keep looping until there are nodes still to be checked
while queue:
# pop shallowest node (first node) from queue
node = queue.pop(0)
explored.append(node)
neighbours = graph[node]
# add neighbours of node to queue
for neighbour in neighbours:
if neighbour not in visited:
queue.append(neighbour)
visited.append(neighbour)
levels[neighbour]= levels[node]+1
# print(neighbour, ">>", levels[neighbour])
print(levels)
return explored
ans = bfs_connected_component(graph,'A') # returns ['A', 'B', 'C', 'E', 'D', 'F', 'G']
print(ans)
回答by Shalan
Yeah, this code only visits the nodes in a breadth-first fashion. This by itself is a useful thing to do for many applications (for example finding shortest paths in an unweighted graph)
是的，此代码仅以广度优先的方式访问节点。对于许多应用程序来说，这本身就是一件有用的事情（例如在未加权的图中找到最短路径）
To actually return the BFS tree would require some additional work. You can think about either storing a list of children for each node, or returning pairs of (node, parent-node). Either representation should allow you to figure out the structure of the tree.
要真正返回 BFS 树需要一些额外的工作。您可以考虑为每个节点存储一个子节点列表，或者返回（节点，父节点）对。任何一种表示都应该允许您找出树的结构。
Another thing to note here, is that the code uses python lists as a queue, which is not a good idea. Because removing the first element from a list, requires O(n) time.
这里要注意的另一件事是，代码使用 python 列表作为队列，这不是一个好主意。因为从列表中删除第一个元素需要 O(n) 时间。
