BFS又名广度优先搜索,和DFS算法一样都是递归算法,不同的是,BFS算法通过队列,在避免循环的同时遍历目标所有节点。
以具有5个节点的无向图为例,如下图:
从节点0开始,BFS算法首先将其放入Visited列表并将其所有相邻节点放入队列。
接下来,访问队列前面的节点1,并转到节点1相邻的节点。因为节点0已经被访问过,所以访问节点2。
节点2有一个未访问的相邻节点4,但因为节点4在队列的最后,因此我们要先访问位于队列前面的节点3。
队列中只剩下节点4没有被访问,所以最后访问节点4。
至此,已经完成了此无向图的广度优先遍历。
create a queue Q mark v as visited and put v into Q while Q is non-empty remove the head u of Q mark and enqueue all (unvisited) neighbours of u
import collections def bfs(graph, root): visited, queue = set(), collections.deque([root]) visited.add(root) while queue: vertex = queue.popleft() print(str(vertex) + " ", end="") for neighbour in graph[vertex]: if neighbour not in visited: visited.add(neighbour) queue.append(neighbour) if __name__ == '__main__': graph = {0: [1, 2], 1: [2], 2: [3], 3: [1, 2]} print("Following is Breadth First Traversal: ") bfs(graph, 0)
以上是深入解析BFS算法原理,带图解说明,并附带Python代码实现BFS算法的详细内容。更多信息请关注PHP中文网其他相关文章!