Graph Traversal: Depth First Search and Breadth First Search

Graph traversal is a fundamental concept in computer science that involves visiting all the vertices of a graph in a systematic manner. Two primary techniques for graph traversal are Depth First Search (DFS) and Breadth First Search (BFS).

1. Depth First Search (DFS)

DFS is a traversal technique that explores as far as possible along one branch before backtracking.

✅ Properties:

✔ Uses a stack (either explicit or recursion-based). ✔ Efficient for exploring connected components. ✔ Suitable for problems like cycle detection and pathfinding. ❌ Can get stuck in infinite loops if cycles exist (without tracking visited nodes).

📌 Example:

For a graph:

   0
  / \
 1   2
 |   |
 3   4

DFS starting from 0: 0 → 1 → 3 → 2 → 4

🔍 Implementation (Python):

# Using recursion
def dfs(graph, node, visited):
    if node not in visited:
        print(node, end=' ')
        visited.add(node)
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)

# Example graph representation
graph = {0: [1, 2], 1: [3], 2: [4], 3: [], 4: []}
visited = set()
dfs(graph, 0, visited)

---

2. Breadth First Search (BFS)

BFS is a traversal technique that explores all neighbors of a vertex before moving to the next level.

✅ Properties:

✔ Uses a queue. ✔ Finds the shortest path in an unweighted graph. ✔ Useful in network broadcasting and shortest-path problems. ❌ Requires more memory than DFS (storing all neighbors at a level).

📌 Example:

For a graph:

   0
  / \
 1   2
 |   |
 3   4

BFS starting from 0: 0 → 1 → 2 → 3 → 4

🔍 Implementation (Python):

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node, end=' ')
            visited.add(node)
            queue.extend(graph[node])

# Example graph representation
bfs(graph, 0)

---

Comparison: DFS vs. BFS

Feature	DFS	BFS
Data Structure	Stack (or Recursion)	Queue
Space Complexity	O(V) (recursive calls)	O(V) (queue storage)
Best for	Deep exploration, cycle detection	Shortest paths, level-order traversal
Complexity	O(V + E)	O(V + E)

Both DFS and BFS have their own use cases, and the choice between them depends on the problem at hand.