时间戳

首页 > 解决方案 > 在有向树的广度优先搜索中跟踪深度

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

问题描述

我正在尝试查找根与正在遍历的节点的深度之间的距离，例如，如果我有一个表示树的以下邻接列表，{ 1: [2, 3], 2: [4], 3: [5]} 则会创建如下所示的关联列表，[0, 1, 1, 2, 2]表示每个节点的级别.

我有以下代码，看不到我要在哪里添加计数功能等，理想情况下，这也可以处理交叉和后边缘

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)

标签： pythontreebreadth-first-search

解决方案

您可以将节点及其级别作为元组排队，而不是仅将节点排队，并且当您将节点排队时，它总是与当前级别加一耦合，因此当您将节点出列并将节点附加到您时，visit_order您也可以获得元组中节点的级别：

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]

推荐阅读