Breadth First Search (BFS) Algorithm for Graphs

Breadth First Search (BFS) graph traversal ka ek foundational algorithm hai jo source vertex se start karke pehle sabhi immediate neighbor vertices (distance 1) ko explore karta hai, fir distance 2 ke vertices ko, and so on level by level. BFS ek FIFO Queue aur ek Visited Boolean Array use karta hai taaki cycles me infinite loop na bane.

BFS Algorithm

BFS(G, startVertex)
1. Initialize visited[V] = {FALSE}
2. Create empty Queue Q
3. Mark visited[startVertex] = TRUE
4. ENQUEUE(Q, startVertex)
5. While Q is not empty do:
6.     u = DEQUEUE(Q)
7.     Print u
8.     For each neighbor v adjacent to u do:
9.         If visited[v] == FALSE then:
10.            visited[v] = TRUE
11.            ENQUEUE(Q, v)
12. End While

Graph:
        (0)
       /   \
     (1)   (2)
      |     |
     (3)   (4)

BFS Traversal starting from 0:
Level 0: 0
Level 1: 1, 2
Level 2: 3, 4
Output: 0 -> 1 -> 2 -> 3 -> 4

Complexity and Applications

• Time Complexity: O(V + E) jab Adjacency List use hoti hai; O(V^2) jab Adjacency Matrix use hoti hai.
• Space Complexity: O(V) visited array aur queue memory ke liye.
• Key Applications: Unweighted graph me Shortest Path find karna, Connected Components count karna, Cycle detection in undirected graphs, Bipartite graph verification.

Agli post me hum cover karenge Depth First Search (DFS) Algorithm for Graphs.