在有向树的广度优先搜索中跟踪深度

本文介绍了在有向树的广度优先搜索中跟踪深度的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在尝试查找根与要遍历的节点深度之间的距离，例如，如果我有以下表示树 {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]