Visualization: Draw and Analyze Graphs | Data Structures

Learn how to trace the two fundamental graph traversal algorithms: Breadth-First Search (BFS) and Depth-First Search (DFS).

Graph Setup

Consider the following directed graph:

    ( 0 ) --------> ( 1 )
      |             /   \
      |           /       \
      v         v           v
    ( 2 ) <--- ( 3 ) ----> ( 4 )

Adjacency List:

0 -> [1, 2]
1 -> [3, 4]
2 -> []
3 -> [2, 4]
4 -> []

1. Breadth-First Search (BFS) Walkthrough

BFS explores outward in expanding concentric waves. It uses a FIFO Queue and a Visited Set.

Goal: BFS starting from Vertex 0

Queue: [ 0 ], Visited: { 0 }

Step 1: Dequeue 0. Neighbors: 1, 2.
        Add 1 and 2 to Queue.
        Queue: [ 1, 2 ], Visited: { 0, 1, 2 }
        Order: 0

Step 2: Dequeue 1. Neighbors: 3, 4.
        Add 3 and 4 to Queue.
        Queue: [ 2, 3, 4 ], Visited: { 0, 1, 2, 3, 4 }
        Order: 0, 1

Step 3: Dequeue 2. No neighbors.
        Queue: [ 3, 4 ]
        Order: 0, 1, 2

Step 4: Dequeue 3. Neighbors: 2 (already visited!), 4 (already visited!).
        Queue: [ 4 ]
        Order: 0, 1, 2, 3

Step 5: Dequeue 4. No neighbors.
        Queue: []
        Order: 0, 1, 2, 3, 4

BFS Traversal Order: 0, 1, 2, 3, 4

fun bfs(start: Int, adjList: Array<List<Int>>) {
    val visited = BooleanArray(adjList.size)
    val queue = ArrayDeque<Int>()

    visited[start] = true
    queue.addLast(start)

    while (queue.isNotEmpty()) {
        val curr = queue.removeFirst()
        print("$curr ")

        for (neighbor in adjList[curr]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true
                queue.addLast(neighbor)
            }
        }
    }
}

2. Depth-First Search (DFS) Walkthrough

DFS dives as deep as possible along each branch before backtracking. It uses the Call Stack (or an explicit Stack).

Goal: DFS starting from Vertex 0

dfs(0)
  visit 0
  call dfs(1)
    visit 1
    call dfs(3)
      visit 3
      call dfs(2)
        visit 2 (returns)
      call dfs(4)
        visit 4 (returns)
      (3 returns)
    (1 returns)
  neighbor 2 already visited!
  (0 returns)

DFS Traversal Order: 0, 1, 3, 2, 4

fun dfs(curr: Int, adjList: Array<List<Int>>, visited: BooleanArray) {
    visited[curr] = true
    print("$curr ")

    for (neighbor in adjList[curr]) {
        if (!visited[neighbor]) {
            dfs(neighbor, adjList, visited)
        }
    }
}

Complexity Analysis

For both BFS and DFS:

Time Complexity: O(V + E) (Every vertex is visited once, every edge is examined once).
Space Complexity: O(V) (To store visited set and queue/stack frames).

Summary

BFS explores horizontally level-by-level using a Queue (finds the shortest path on unweighted graphs).
DFS dives deep vertically using Recursion/Stack (detects cycles and solves topological sorting).