在有向树的广度优先搜索中跟踪深度 [英] Tracking depth in a breadth first search of a directed tree
问题描述
我正在尝试查找根与要遍历的节点深度之间的距离,例如,如果我有以下表示树 {1的邻接表:[2, 3],2:[4],3:[5]}
会创建如下所示的关联列表 [0、1、1、2、2]
表示每个节点的级别。
I'm trying to find the distance between the root and the depth of the node that is being traversed, for example if I had a the following adjancency list representing the tree { 1: [2, 3], 2: [4], 3: [5]}
an associated list like the following would be created [0, 1, 1, 2, 2]
denoting the level of each node.
我有以下代码,看不到要在何处添加计数功能等,理想情况下,也会处理后边缘和后边缘
I have the following code and can't see where I'm meant to add counting functionality etc, ideally this would deal with cross and back edges as well
def bfs(graph, root):
seen, queue = set([root]), collections.deque([root])
visit_order = []
while queue:
vertex = queue.popleft()
visit_order.append(vertex)
for node in graph[vertex]:
if node not in seen:
seen.add(node)
queue.append(node)
print(visit_order)
推荐答案
仅对节点进行排队,您可以将节点及其级别作为元组排队,并且当排队一个节点时,它总是与当前级别加一,因此当您将一个节点出队并将该节点附加到时visit_order
您还可以从元组中获取节点的级别:
Instead of queuing just the nodes, you can queue the nodes and their levels as tuples, and when you enqueue a node it's always coupled with the current level plus one, so that when you dequeue a node and append the node to visit_order
you also get the level of the node from the tuple:
import collections
def bfs(graph, root):
seen, queue = {root}, collections.deque([(root, 0)])
visit_order = []
levels = []
while queue:
vertex, level = queue.popleft()
visit_order.append(vertex)
levels.append(level)
for node in graph.get(vertex, []):
if node not in seen:
seen.add(node)
queue.append((node, level + 1))
print(visit_order)
print(levels)
这样:
bfs({ 1: [2, 3], 2: [4], 3: [5]}, 1)
将输出:
[1, 2, 3, 4, 5]
[0, 1, 1, 2, 2]
这篇关于在有向树的广度优先搜索中跟踪深度的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!