What is BFS in Graph: Explanation and Example

BFS (Breadth-First Search) is a graph traversal method that explores nodes level by level, starting from a chosen node and visiting all its neighbors before moving deeper. It uses a queue to keep track of nodes to visit next, ensuring the shortest path in unweighted graphs.

How It Works

BFS starts at a selected node, called the source, and explores all its immediate neighbors first. Imagine you are in a building and want to visit every room floor by floor. You first check all rooms on the current floor before going to the next floor. This way, BFS visits nodes in layers or levels.

It uses a queue to remember which nodes to visit next. When a node is visited, all its unvisited neighbors are added to the queue. This process repeats until all reachable nodes are visited. This approach guarantees that the first time you reach a node, you have found the shortest path to it in terms of the number of edges.

Example

This example shows BFS on a simple graph represented by an adjacency list. It prints nodes in the order they are visited starting from node 0.

python

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            order.append(node)
            for neighbor in graph[node]:
                if neighbor not in visited and neighbor not in queue:
                    queue.append(neighbor)
    return order

# Graph as adjacency list
graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 5],
    3: [1],
    4: [1, 5],
    5: [2, 4]
}

print(bfs(graph, 0))

Output

[0, 1, 2, 3, 4, 5]

When to Use

BFS is useful when you need to find the shortest path in an unweighted graph, such as in social networks to find the shortest connection between people, or in maps to find the shortest route without weights. It is also used in algorithms like finding connected components, testing bipartiteness, and in web crawlers to explore links level by level.

Because BFS explores neighbors first, it is ideal when you want to explore all options closest to the start before moving further away.

Key Points

• BFS explores nodes level by level using a queue.
• It finds the shortest path in unweighted graphs.
• It starts from a source node and visits all reachable nodes.
• Useful in many real-world problems like shortest path, social networks, and web crawling.

Key Takeaways

BFS visits graph nodes in layers, exploring all neighbors before going deeper.

It uses a queue to keep track of nodes to visit next.

BFS finds the shortest path in unweighted graphs.

It is useful for problems like shortest path, connectivity, and level-order exploration.