An in-depth analysis of the principles of the BFS algorithm, with illustrated explanations, and Python code to implement the BFS algorithm.

BFS, also known as breadth-first search, is a recursive algorithm like the DFS algorithm. The difference is that the BFS algorithm uses a queue to traverse all the target nodes while avoiding loops.

Illustration of the working principle of the BFS algorithm

Take an undirected graph with 5 nodes as an example, as shown below:

Starting from node 0, the BFS algorithm first puts it into the Visited list and puts all its neighboring nodes into the queue.

Next, access node 1 at the front of the queue and go to nodes adjacent to node 1. Because node 0 has already been visited, node 2 is visited.

Node 2 has an unvisited adjacent node 4, but because node 4 is at the end of the queue, we need to visit the front of the queue first Node 3.

Only node 4 is left in the queue that has not been visited, so node 4 is visited last.

At this point, the breadth-first traversal of this undirected graph has been completed.

Pseudocode of BFS algorithm

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

Python code to implement BFS algorithm

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)

The above is the detailed content of An in-depth analysis of the principles of the BFS algorithm, with illustrated explanations, and Python code to implement the BFS algorithm.. For more information, please follow other related articles on the PHP Chinese website!