我在网上找到了一个例子,但是,仅返回 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']
最佳答案
您可以通过首先将级别 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)
关于Python 实现广度优先搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46383493/