BFS and DFS in Graphs

Let’s go step by step on how BFS and DFS are implemented in graphs.

---

1️⃣ Graph Representation

Graphs are usually represented in two ways:

1. Adjacency List (preferred for sparse graphs)

graph = { 0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2] }

2. Adjacency Matrix (for dense graphs)

graph = [ [0, 1, 1, 0], [1, 0, 0, 1], [1, 0, 0, 1], [0, 1, 1, 0] ]

---

2️⃣ BFS Implementation (Python)

Breadth-First Search explores nodes level by level:

from collections import deque

def bfs(graph, start):
    visited = set()       # keep track of visited nodes
    queue = deque([start])
    visited.add(start)
   
    while queue:
        node = queue.popleft()
        print(node, end=" ")
       
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Example usage

bfs(graph, 0)

Output for the example graph:

0 1 2 3

Key points:

Uses queue to process nodes level by level.

Visited set prevents cycles.

---

3️⃣ DFS Implementation (Recursive)

Depth-First Search goes deep before backtracking:

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
   
    visited.add(node)
    print(node, end=" ")
   
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

Example usage

dfs(graph, 0)

Output:

0 1 3 2

Notes:

Uses recursion to go deep.

Visited set prevents infinite loops in cycles.

---

4️⃣ DFS Implementation (Iterative / Stack-Based)

def dfs_iter(graph, start):
    visited = set()
    stack = [start]
   
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node, end=" ")
            # Add neighbors to stack
            for neighbor in graph[node]:
                stack.append(neighbor)

dfs_iter(graph, 0)

Same logic as recursive DFS, but uses a stack explicitly.

---

5️⃣ Handling Disconnected Graphs

Graph may have multiple components.

Run BFS/DFS from every unvisited node:

visited = set()
for node in graph:
    if node not in visited:
        dfs(graph, node, visited)

---

✅ Summary of Implementation

Traversal Data Structure Steps

BFS Queue Visit node → enqueue neighbors → mark visited → repeat DFS (recursive) Call stack Visit node → recursively visit unvisited neighbors DFS (iterative) Stack Pop node → push neighbors → mark visited → repeat Disconnected Graph Queue/Stack + loop Run BFS/DFS on each unvisited node