How we do traversal in Graphs because graphs do not have a natural hierarchy

Unlike trees, graphs don’t have a natural hierarchy, so BFS and DFS need extra bookkeeping to avoid cycles and repeated visits. Let’s break it down carefully.

---

1️⃣ Why Graphs Are Different

Trees are acyclic → no cycles, one path to each node.

Graphs can have:

Cycles → nodes may loop back

Disconnected components → not all nodes reachable from a single start

Problem: Without precautions, DFS/BFS may visit nodes infinitely in a cycle.

---

2️⃣ BFS on Graphs

Breadth-First Search explores level by level, using a queue.

Steps:

1. Start at a source node.
2. Mark it as visited (to avoid revisiting).
3. Enqueue the source node.
4. While queue is not empty:

Dequeue a node u.

Process u.

Enqueue all unvisited neighbors of u, and mark them visited.

Visited set/array is essential to avoid cycles.

Pseudocode (Adjacency List)

def bfs(graph, start):
    visited = set()
    queue = [start]
    visited.add(start)
   
    while queue:
        node = queue.pop(0)
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

---

3️⃣ DFS on Graphs

Depth-First Search explores as deep as possible before backtracking, using a stack (or recursion).

Steps:

1. Start at a source node.
2. Mark it as visited.
3. Recur or push all unvisited neighbors onto stack.

Visited set/array is essential to avoid infinite loops in cycles.

Recursive DFS Pseudocode

def dfs(graph, node, visited):
    visited.add(node)
    print(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

Iterative DFS (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)
            for neighbor in graph[node]:
                stack.append(neighbor)

---

4️⃣ Handling Disconnected Graphs

If the graph is disconnected, run BFS/DFS from each unvisited node:

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

---

5️⃣ Key Points

Aspect Graph Tree

Cycles Possible → must track visited Not possible Disconnected Possible → may need multiple runs Usually one connected tree Data Structure BFS → queue, DFS → stack/recursion Same, but no cycle checks needed Visited Tracking Essential Optional (tree guarantees no revisits)

---

✅ Summary

BFS and DFS work on graphs, but you must track visited nodes.

Queue (BFS) or Stack/Recursion (DFS) are used just like in trees.

Extra step: check visited to avoid infinite loops and repeated processing.

For disconnected graphs, iterate over all nodes.