Skip to main content
Practice

Breadth-First Search (BFS) Implementation Guide

1. Using a Queue​

  • BFS uses a queue to manage the nodes that need to be explored. It traverses nodes level by level using the queue.
Queue Example
def bfs(graph, start):
    visited = []
    queue = [start]

    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            # Avoid duplicates using a list
            queue.extend([n for n in graph[node] if n not in visited])

    return visited

2. Level-By-Level Traversal​

  • BFS explores adjacent nodes for each node level by level. This utilizes the FIFO (First In, First Out) property of queues.
Level-By-Level Traversal Example
while queue:
    node = queue.pop(0)
    if node not in visited:
        visited.append(node)
        # Avoid duplicates using a list
        queue.extend([n for n in graph[node] if n not in visited])

Time Complexity​

  1. Time Complexity: (O(V + E))

    • Where V is the number of vertices and E is the number of edges. Each vertex is visited once, and each edge is checked once.

  2. Shortest Path Search: BFS is effective in finding the shortest path from the start node to the target node in an undirected graph.

  3. Wide Range Exploration: BFS effectively explores a wide range of nodes through level-based traversal.

Want to learn more?

Join CodeFriends Plus membership or enroll in a course to start your journey.