Python实现广度优先搜索
Python实现广度优先搜索
提问于 2017-09-24 03:29:02
我在网上找到了一个例子，然而，只返回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']回答 2
Stack Overflow用户
回答已采纳
发布于 2017-09-24 03:52:49
您可以通过首先将级别0指定给开始节点来跟踪每个节点的级别。然后，为节点X的每个邻居分配级别level_of_X + 1。
此外，您的代码会多次将同一节点推入队列。我使用了一个单独的列表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)Stack Overflow用户
发布于 2017-09-24 03:47:40
是的，这段代码只以广度优先的方式访问节点。对于许多应用程序来说，这本身就是一件很有用的事情(例如，在未加权的图中查找最短路径)
要真正返回BFS树，需要做一些额外的工作。您可以考虑为每个节点存储一个子节点列表，或者返回成对的(node，parent-node)。任何一种表示都应该允许您找出树的结构。
这里要注意的另一件事是，代码使用python列表作为队列，这不是一个好主意。因为从列表中删除第一个元素需要O(n)时间。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/46383493
复制相关文章
相似问题
腾讯云开发者
