Python构造BFS

Question

我在网上发现了许多BFS示例代码，但是输入与我的格式不一样，输出也不像预期的那样。

我有一个节点nodesList列表，每个节点对象都有一个节点id，并包含neighboursList中其相邻节点的所有id。现在，我想使用BFS构建一个nodesList。据我所知，如果我知道，可以进行计算并构造一个BFS：

• 哪些节点位于BFS级别1的每个级别上:根，等等
• BFS中每个节点的父节点。
• BFS中每个节点的子节点。
• BFS中每个节点的节点id

因此，我创建了另一个名为BFSnode的类，它存储我需要的信息。虽然我总是可以找到前两个层次，因为我不知道输入图有多大，但我很困惑如何使用递归动态地找到这些信息。由于我不熟悉动态编程和递归，如果有人能帮助我，我将不胜感激。非常感谢。

Answer 1

要进行广度优先搜索，您不需要使用递归或动态编程。

宽度优先搜索通常使用队列数据结构：

1. 首先添加根节点或要从队列开始搜索的节点。
2. 当队列中有节点时，首先将下一个节点排出队列。无论您需要如何处理它，并为它的子级排队。
3. 当队列为空时，搜索结束。

粗略代码(未经测试)：

class Node(object):
    def __init__(self, val):
        self.val = val
        self.children = []

def breadth_first_search(root):
    next_nodes = Queue()
    next_nodes.enqueue(root)

    while not next_nodes.empty():
        cur_node = next_nodes.dequeue()

        # Do something with cur_node

        for child in cur_node.children:
            next_nodes.enqueue(child)

我假设了一个队列对象的存在，它支持队列、去队列和空，这不是python中的内置内容。您可以编写自己的、使用列表，或者使用collections.deque与append()和popleft()一起使用，而不是进行队列和排队列。

我还假设这个图没有循环。看起来你在和树一起工作，所以这可能是一个安全的假设。