Write the full details of BFS with example

1. Introduction

Breadth-First Search (BFS) is a graph traversal algorithm used to explore the nodes and edges of a graph in a layer-wise (or level-order) manner. It starts from a source node and explores all of its neighbors before moving to the next level neighbors.

• Data structure used: Queue
• Type: Uninformed or blind search (no heuristic used)
• Applicable on: Graphs (both directed and undirected), Trees

2. Applications of BFS

• Finding the shortest path in unweighted graphs
• Web crawling
• Peer-to-peer networks like BitTorrent
• GPS navigation
• Social networking websites
• Solving puzzles like sliding tiles or Rubik’s cube

3. Properties of BFS

4. BFS Algorithm (Steps)

Input:

• A graph G = (V, E)
• A source vertex s

Output:

• Traversal order of vertices starting from s

Steps:

1. Create a queue and a visited array or set.
2. Mark the source node as visited and enqueue it.
3. While the queue is not empty:

• Dequeue a node from the queue, call it current
• For each neighbor of current:
  • If the neighbor is not visited:
  • Mark it as visited
  • Enqueue it

5. BFS Pseudocode

BFS(Graph, start):
    create a queue Q
    mark start as visited
    enqueue start into Q

    while Q is not empty:
        current = Q.dequeue()
        print(current)

        for each neighbor of current:
            if neighbor is not visited:
                mark neighbor as visited
                Q.enqueue(neighbor)

6. BFS Example (Step-by-step)

Graph Representation

Let’s consider the following undirected graph:

     A
    / \
   B   C
  / \   \
 D   E   F

Adjacency List:

A: B, C
B: A, D, E
C: A, F
D: B
E: B
F: C

Step-by-Step BFS Traversal from A

1. Initialize:

• Visited: {A}
• Queue: [A]
• Output: []

1. Visit A:

• Neighbors: B, C
• Mark B, C as visited
• Queue: [B, C]
• Output: [A]

1. Visit B:

• Neighbors: A, D, E
• A is already visited
• Mark D, E as visited
• Queue: [C, D, E]
• Output: [A, B]

1. Visit C:

• Neighbors: A, F
• A is visited
• Mark F as visited
• Queue: [D, E, F]
• Output: [A, B, C]

1. Visit D:

• Neighbor: B (already visited)
• Queue: [E, F]
• Output: [A, B, C, D]

1. Visit E:

• Neighbor: B (already visited)
• Queue: [F]
• Output: [A, B, C, D, E]

1. Visit F:

• Neighbor: C (already visited)
• Queue: []
• Output: [A, B, C, D, E, F]

Final BFS Traversal Output:

A → B → C → D → E → F

7. Python Implementation

from collections import deque

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

    while queue:
        current = queue.popleft()
        print(current, end=' ')

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

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

bfs(graph, 'A')

Output:

A B C D E F

8. BFS vs DFS

9. Advantages of BFS

• Guarantees shortest path in unweighted graphs.
• Useful for level-order traversal.
• Detects if a path exists between two nodes.

10. Disadvantages of BFS

• High memory usage due to storing all frontier nodes.
• Inefficient in graphs with large branching factors or depth.