Python 实施 Breadth-First 搜索

Question

网上找了一个例子，但是只返回BFS元素的序列是不够计算的。假设根是 BFS 树的第一层，那么它的 children 是第二层，等等。我怎么知道它们在哪一层，以及每个节点的 parent 来自下面的代码（我将创建一个 object 来存储它的 parent 和树级别）?

# 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']

Answer 1

是的，此代码仅以广度优先方式访问节点。这本身对许多应用程序来说都是一件有用的事情（例如在未加权的图中找到最短路径）

实际上 return BFS 树需要一些额外的工作。您可以考虑为每个节点存储一个子节点列表，或者 returning 对（节点，父节点）。任何一种表示都应该让您弄清楚树的结构。

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

Answer 2

您可以通过首先将级别 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)

Python 实施 Breadth-First 搜索

Python Implement Breadth-First Search

python

graph-theory

breadth-first-search