What Is BFS in Data Structure With Example?

The Breadth-First Search (BFS) algorithm is a fundamental graph traversal algorithm used in data structures. It explores all the vertices of a graph in breadth-first order, visiting all neighboring vertices before moving to the next level of vertices. In this article, we will dive into the details of BFS and provide an example to illustrate its functionality.

What is Breadth-First Search?

Breadth-First Search is a graph traversal algorithm that starts at a specified vertex (or node) of a graph and explores all its neighboring vertices before moving on to their neighbors. It systematically visits all the vertices of the graph, ensuring that no vertex is left unvisited.

The BFS algorithm operates like waves propagating through the graph, exploring vertices one level at a time. It uses a queue data structure to keep track of the vertices to visit, ensuring that they are visited in the order they were discovered.

How Does Breadth-First Search Work?

Let’s understand how BFS works step by step:

1. Step 1: Start at a specific vertex and enqueue it into the queue.
2. Step 2: Dequeue a vertex from the queue and visit it.
3. Step 3: Enqueue all neighboring vertices of the visited vertex that have not been visited yet.
4. Step 4: Repeat steps 2 and 3 until the queue becomes empty.

BFS ensures that each vertex is visited exactly once and no vertex is visited before its neighbors. This guarantees that BFS explores all reachable vertices from the starting point.

Breadth-First Search Example

Let’s consider a simple graph to demonstrate the BFS algorithm:

   A --- B
  / \   /
 /   \ /
C --- D

Starting from vertex A, let’s walk through the BFS algorithm:

1. Step 1: Enqueue vertex A.
2. Step 2: Dequeue A and visit it. Mark A as visited.
3. Step 3: Enqueue B and C.
4. Step 4: Dequeue B and visit it.

   Mark B as visited.

5. Step 5: Enqueue D.
6. Step 6: Dequeue C and visit it. Mark C as visited.
7. Step 7: Dequeue D and visit it. Mark D as visited.

The order of visited vertices in this example is: A, B, C, D. BFS explores the vertices in breadth-first order, visiting all neighbors of a vertex before moving to the next level of vertices.

BFS Implementation in Python

To implement BFS in Python, we can use a queue data structure and an adjacency list representation of the graph. Here’s an example implementation:

from collections import deque

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

    while queue:
        vertex = queue.popleft()
        print(vertex)

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

# Example usage
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

bfs(graph, 'A')

In this Python implementation, we use a deque from the collections module to represent the queue. We also use a set to keep track of visited vertices to ensure efficient lookup.

By using the BFS algorithm, we can efficiently traverse graphs and visit all vertices in breadth-first order. This algorithm is widely used in various applications, such as finding the shortest path between two vertices and analyzing network connections.

Conclusion

Breadth-First Search is a powerful graph traversal algorithm that systematically explores all vertices of a graph in breadth-first order. It guarantees that each vertex is visited exactly once, ensuring that no vertex is left unvisited. By using a queue data structure, BFS efficiently explores graphs and finds various applications in computer science and data structures.

Now that you understand what BFS is and how it works, you can apply this knowledge to solve graph-related problems and analyze network structures effectively.