Python实现广度优先搜索

Question

Python实现广度优先搜索

7

我在网上找到了一个例子，但是仅返回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']

- user5575144

这篇帖子属于CodeReview网站。 - AmiNadimi

1

很抱歉，这不属于代码审查范畴。它要求添加新功能（主要是遍历中节点的前驱）。在代码审查中，请求添加新功能是不适当的话题。有关更多信息，请参阅我们针对Stack Overflow用户的指南。 - Zeta

理想情况下，explored 应该是一个 set()，否则可能会达到 O(N*N) 的时间复杂度。另外，为了更快的 pop(0)，queue 应该是一个 dequeue。 - Rusty Rob

2个回答

2

是的，这段代码只以广度优先的方式访问节点。这本身对于许多应用程序来说是有用的（例如在无权图中查找最短路径）。

要实际返回BFS树需要进行一些额外的工作。您可以考虑为每个节点存储一个子节点列表，或者返回(node，parent-node)对。任何一种表示都应允许您确定树的结构。

还有一件事要注意，这里的代码使用python列表作为队列，这不是一个好主意。因为从列表中删除第一个元素需要O(n)时间。

- Shalan

然而，由于使用了 pop，所以它的时间复杂度为 O(1)。实际上，它是一个栈，而不是队列。 - Jeff Learman

1

当您将索引传递给 pop 时，它会弹出该索引处的元素。在这种情况下，由于传递了索引 _0_，因此它将删除列表的第一个元素。因此，该列表被用作队列。 - Shalan

糟糕！pop(0)确实可以将其变成队列，但是效率非常低下，因为正如你所指出的，pop(0)的时间复杂度为O(N)。更好的方法是使用deque，或者只需将列表用作堆栈（使用pop()），这在这里同样有效。如果邻居们一开始没有排序，那么没有显着的区别。 - Jeff Learman

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Anonta · Accepted Answer

您可以通过先将起始节点指定为级别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)