Python递归实现图的广度优先搜索算法

2023-04-15 00:00:00 算法 递归 广度

广度优先搜索算法（BFS）是一种在图中搜索节点的算法，它从起点开始，逐层向外遍历节点直到找到目标节点或遍历完整张图。BFS使用队列来实现，每次取出最早加入队列的节点来进行操作。

具体实现过程如下：

  1. 创建一个队列，用于保存待遍历的节点。
  2. 将起点节点加入队列，并标记为已访问。
  3. 从队列中取出第一个未被访问过的节点，如果该节点为目标节点，则返回结果；否则将其所有相邻且未被访问过的节点加入队列中。
  4. 重复步骤3，直到队列为空。

以下是Python的递归实现演示代码：

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.adj = [[] for i in range(vertices)]

    def add_edge(self, u, v):
        self.adj[u].append(v)

    def BFS(self, queue, visited, res):
        if not queue:
            return res
        node = queue.pop(0)
        res.append(node)
        for neighbor in self.adj[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)
        return self.BFS(queue, visited, res)

    def BFS_traversal(self, start):
        visited = [False] * self.V
        visited[start] = True
        queue = [start]
        res = []
        res = self.BFS(queue, visited, res)
        return res

g = Graph(7)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 5)
g.add_edge(2, 6)

print("BFS traversal starting from vertex 0:")
res = g.BFS_traversal(0)
print(res)

输出结果为：

BFS traversal starting from vertex 0:
[0, 1, 2, 3, 4, 5, 6]

此代码演示了从节点0开始的BFS遍历结果。在该图中，节点0连接着节点1和节点2，节点1连接着节点3和节点4，节点2连接着节点5和节点6。因此，遍历结果为[0, 1, 2, 3, 4, 5, 6]。

相关文章