Theory - Traversals

Part 1: BFS Traversal of a Graph

Problem Link

Link - bfs traversal of graph

Intuition

Breadth-First Search (BFS) is a graph traversal algorithm that explores vertices level by level, starting from a source vertex. It uses a queue to explore neighbors first before moving deeper into the graph.

Key ideas:

• Visualize it like ripples spreading outward.

• All immediate neighbors are explored before deeper nodes.

• A visited array ensures no cycles or repeated nodes.

• Ideal for shortest path problems in unweighted graphs.

Applications

• Finding shortest path in unweighted graphs

• Peer-to-peer networks like BitTorrent

• Crawling social networks

• Finding connected components

• Solving puzzles with fewest moves

• Broadcasting in a network

Algorithm

1. Create an empty queue q.

2. Create a visited boolean array of size V.

3. Create an empty list result to store the BFS traversal.

4. Start from node 0:

   • Mark as visited.

   • Add to the queue.

5. While the queue is not empty:

   • Remove a node from the queue.

   • Add it to the result.

   • For each unvisited neighbor:

     • Mark visited.

     • Add to the queue.

Code (Java)

class Solution {
    public ArrayList<Integer> bfsOfGraph(int V, ArrayList<ArrayList<Integer>> adj) {
        ArrayList<Integer> result = new ArrayList<>();
        boolean[] visited = new boolean[V];
        Queue<Integer> q = new LinkedList<>();
        
        q.add(0);  // Start BFS from node 0
        visited[0] = true;
        
        while (!q.isEmpty()) {
            int curr = q.poll();
            result.add(curr);
            
            for (int neighbor : adj.get(curr)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.add(neighbor);
                }
            }
        }
        
        return result;
    }
}

Dry Run

Graph:

V = 5  
Edges:  
0 -> 1, 2  
1 -> 3  
2 -> 4

Adjacency List:

0: [1, 2]  
1: [3]  
2: [4]  
3: []  
4: []

Initial State:

visited = [false, false, false, false, false]
queue = [0]
result = []

Step-by-step:

1. Pop 0 → result = [0]

   • Neighbors: 1, 2 → mark visited, add to queue

   • queue = [1, 2]

2. Pop 1 → result = [0, 1]

   • Neighbor: 3 → mark visited, add to queue

   • queue = [2, 3]

3. Pop 2 → result = [0, 1, 2]

   • Neighbor: 4 → mark visited, add to queue

   • queue = [3, 4]

4. Pop 3 → result = [0, 1, 2, 3]

5. Pop 4 → result = [0, 1, 2, 3, 4]

Final Output: [0, 1, 2, 3, 4]

Time and Space Complexity

• Time: O(V + E), where V = vertices, E = edges.

• Space: O(V) for visited array and queue.

Part 2: DFS Traversal of a Graph

Problem Link

Link - Depth first traversal for a graph

Intuition

Depth-First Search (DFS) explores as far down a path as possible before backtracking. It uses recursion or a stack to explore deep paths first, unlike BFS.

Key points:

• Think of exploring one branch fully before moving to the next.

• Uses recursion or manual stack.

• Visited array prevents cycles.

• Suitable for exploring complete components.

Applications

• Topological sort

• Detecting cycles in a graph

• Solving mazes or puzzles

• Finding connected components

• Pathfinding in AI (if implemented with pruning)

• Backtracking algorithms

Algorithm

1. Create a visited boolean array of size V.

2. Create an empty list result.

3. Call dfs(0):

   • Mark the node visited.

   • Add to result.

   • Recur for all unvisited neighbors.

Code (Java)

class Solution {
    public ArrayList<Integer> dfsOfGraph(int V, ArrayList<ArrayList<Integer>> adj) {
        boolean[] visited = new boolean[V];
        ArrayList<Integer> result = new ArrayList<>();
        dfs(0, visited, adj, result);
        return result;
    }
    
    private void dfs(int node, boolean[] visited, ArrayList<ArrayList<Integer>> adj, ArrayList<Integer> result) {
        visited[node] = true;
        result.add(node);
        
        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited, adj, result);
            }
        }
    }
}

Dry Run

Graph:

V = 5  
Edges:  
0 -> 1, 2  
1 -> 3  
2 -> 4

Adjacency List:

0: [1, 2]  
1: [3]  
2: [4]  
3: []  
4: []

Call Stack and Result:

• dfs(0) → result = [0]

  • dfs(1) → result = [0, 1]

    • dfs(3) → result = [0, 1, 3]

  • backtrack

  • dfs(2) → result = [0, 1, 3, 2]

    • dfs(4) → result = [0, 1, 3, 2, 4]

Final Output: [0, 1, 3, 2, 4]

Time and Space Complexity

• Time: O(V + E)

• Space: O(V) for visited array + recursion stack

Summary: BFS vs DFS