Shortest Path in Unweighted Graph Using BFS in DSA C# - Execution Trace

Concept Flow - Shortest Path in Unweighted Graph Using BFS

Start at source node

↓

Initialize queue with source

↓

While queue not empty

↓

Dequeue current node

↓

For each neighbor

↓

Skip

↓

Mark visited, set distance, set parent

↓

Enqueue neighbor

↓

Repeat

↓

Build path from target to source using parents

↓

Return shortest path

Start from the source node, explore neighbors level by level using a queue, track parents to reconstruct shortest path.

Execution Sample

DSA C#

Queue<int> q = new Queue<int>();
q.Enqueue(source);
visited[source] = true;
distance[source] = 0;
while(q.Count > 0) {
  int current = q.Dequeue();
  foreach(var neighbor in graph[current]) {
    if(!visited[neighbor]) {
      visited[neighbor] = true;
      distance[neighbor] = distance[current] + 1;
      parent[neighbor] = current;
      q.Enqueue(neighbor);
    }
  }
}
// Reconstruct path from target to source using parent array

This code finds shortest path distances and parents from source to all reachable nodes using BFS.

Execution Table

Step	Operation	Current Node	Queue State	Visited Set	Distance Array	Parent Array	Visual State
1	Initialize	-	[0]	{0}	[0:0, others:∞]	[0:-1, others:-1]	Graph nodes: 0-5; Start at node 0
2	Dequeue	0	[]	{0}	[0:0, others:∞]	[0:-1, others:-1]	Visit node 0
3	Visit neighbors	0	[]	{0}	[0:0, others:∞]	[0:-1, others:-1]	Neighbors of 0: 1, 2
4	Enqueue neighbor 1	0	[1]	{0,1}	[0:0,1:1, others:∞]	[0:-1,1:0, others:-1]	Mark 1 visited, distance=1, parent=0
5	Enqueue neighbor 2	0	[1,2]	{0,1,2}	[0:0,1:1,2:1, others:∞]	[0:-1,1:0,2:0, others:-1]	Mark 2 visited, distance=1, parent=0
6	Dequeue	1	[2]	{0,1,2}	[0:0,1:1,2:1, others:∞]	[0:-1,1:0,2:0, others:-1]	Visit node 1
7	Visit neighbors	1	[2]	{0,1,2}	[0:0,1:1,2:1, others:∞]	[0:-1,1:0,2:0, others:-1]	Neighbors of 1: 0, 3
8	Skip neighbor 0 (visited)	1	[2]	{0,1,2}	[0:0,1:1,2:1, others:∞]	[0:-1,1:0,2:0, others:-1]	0 already visited
9	Enqueue neighbor 3	1	[2,3]	{0,1,2,3}	[0:0,1:1,2:1,3:2, others:∞]	[0:-1,1:0,2:0,3:1, others:-1]	Mark 3 visited, distance=2, parent=1
10	Dequeue	2	[3]	{0,1,2,3}	[0:0,1:1,2:1,3:2, others:∞]	[0:-1,1:0,2:0,3:1, others:-1]	Visit node 2
11	Visit neighbors	2	[3]	{0,1,2,3}	[0:0,1:1,2:1,3:2, others:∞]	[0:-1,1:0,2:0,3:1, others:-1]	Neighbors of 2: 0, 3, 4
12	Skip neighbor 0 (visited)	2	[3]	{0,1,2,3}	[0:0,1:1,2:1,3:2, others:∞]	[0:-1,1:0,2:0,3:1, others:-1]	0 already visited
13	Skip neighbor 3 (visited)	2	[3]	{0,1,2,3}	[0:0,1:1,2:1,3:2, others:∞]	[0:-1,1:0,2:0,3:1, others:-1]	3 already visited
14	Enqueue neighbor 4	2	[3,4]	{0,1,2,3,4}	[0:0,1:1,2:1,3:2,4:2, others:∞]	[0:-1,1:0,2:0,3:1,4:2, others:-1]	Mark 4 visited, distance=2, parent=2
15	Dequeue	3	[4]	{0,1,2,3,4}	[0:0,1:1,2:1,3:2,4:2, others:∞]	[0:-1,1:0,2:0,3:1,4:2, others:-1]	Visit node 3
16	Visit neighbors	3	[4]	{0,1,2,3,4}	[0:0,1:1,2:1,3:2,4:2, others:∞]	[0:-1,1:0,2:0,3:1,4:2, others:-1]	Neighbors of 3: 1, 2, 5
17	Skip neighbor 1 (visited)	3	[4]	{0,1,2,3,4}	[0:0,1:1,2:1,3:2,4:2, others:∞]	[0:-1,1:0,2:0,3:1,4:2, others:-1]	1 already visited
18	Skip neighbor 2 (visited)	3	[4]	{0,1,2,3,4}	[0:0,1:1,2:1,3:2,4:2, others:∞]	[0:-1,1:0,2:0,3:1,4:2, others:-1]	2 already visited
19	Enqueue neighbor 5	3	[4,5]	{0,1,2,3,4,5}	[0:0,1:1,2:1,3:2,4:2,5:3]	[0:-1,1:0,2:0,3:1,4:2,5:3]	Mark 5 visited, distance=3, parent=3
20	Dequeue	4	[5]	{0,1,2,3,4,5}	[0:0,1:1,2:1,3:2,4:2,5:3]	[0:-1,1:0,2:0,3:1,4:2,5:3]	Visit node 4
21	Visit neighbors	4	[5]	{0,1,2,3,4,5}	[0:0,1:1,2:1,3:2,4:2,5:3]	[0:-1,1:0,2:0,3:1,4:2,5:3]	Neighbors of 4: 2
22	Skip neighbor 2 (visited)	4	[5]	{0,1,2,3,4,5}	[0:0,1:1,2:1,3:2,4:2,5:3]	[0:-1,1:0,2:0,3:1,4:2,5:3]	2 already visited
23	Dequeue	5	[]	{0,1,2,3,4,5}	[0:0,1:1,2:1,3:2,4:2,5:3]	[0:-1,1:0,2:0,3:1,4:2,5:3]	Visit node 5
24	Visit neighbors	5	[]	{0,1,2,3,4,5}	[0:0,1:1,2:1,3:2,4:2,5:3]	[0:-1,1:0,2:0,3:1,4:2,5:3]	Neighbors of 5: 3
25	Skip neighbor 3 (visited)	5	[]	{0,1,2,3,4,5}	[0:0,1:1,2:1,3:2,4:2,5:3]	[0:-1,1:0,2:0,3:1,4:2,5:3]	3 already visited
26	Queue empty	-	[]	{0,1,2,3,4,5}	[0:0,1:1,2:1,3:2,4:2,5:3]	[0:-1,1:0,2:0,3:1,4:2,5:3]	BFS complete, shortest distances and parents set

💡 Queue is empty, all reachable nodes visited, BFS ends

Variable Tracker

Variable	Start	After Step 5	After Step 9	After Step 14	After Step 19	After Step 26 (final)
Queue	[]	[1,2]	[2,3]	[3,4]	[4,5]	[]
Visited Set	{}	{0,1,2}	{0,1,2,3}	{0,1,2,3,4}	{0,1,2,3,4,5}	{0,1,2,3,4,5}
Distance Array	[∞,∞,∞,∞,∞,∞]	[0,1,1,∞,∞,∞]	[0,1,1,2,∞,∞]	[0,1,1,2,2,∞]	[0,1,1,2,2,3]	[0,1,1,2,2,3]
Parent Array	[-1,-1,-1,-1,-1,-1]	[-1,0,0,-1,-1,-1]	[-1,0,0,1,-1,-1]	[-1,0,0,1,2,-1]	[-1,0,0,1,2,3]	[-1,0,0,1,2,3]

Key Moments - 3 Insights

Why do we mark a neighbor as visited immediately when we enqueue it, not when we dequeue it?

Marking visited when enqueuing (see steps 4,5,9) prevents adding the same node multiple times to the queue, avoiding repeated processing and infinite loops.

Why do we use a parent array during BFS?

The parent array (see steps 4,5,9,14,19) helps reconstruct the shortest path by storing from which node we reached the current node.

What happens if the target node is not reachable from the source?

If unreachable, BFS never visits it, so its distance remains infinity and parent stays -1, indicating no path found.

Visual Quiz - 3 Questions

Look at the execution table at step 14. What is the distance value for node 4?

A 2

B 1

C 3

D ∞

💡 Hint

Check the 'Distance Array' column at step 14 in the execution_table.

At which step does node 5 get enqueued for the first time?

A Step 17

B Step 19

C Step 22

D Step 25

💡 Hint

Look for the first 'Enqueue neighbor 5' operation in the execution_table.

If we remove the visited check before enqueueing neighbors, what would happen to the queue?

A It would become empty immediately.

B It would remain the same.

C It would contain duplicate nodes.

D It would only contain the source node.

💡 Hint

Refer to the key moment about marking visited when enqueuing to avoid duplicates.

Concept Snapshot

Shortest Path in Unweighted Graph Using BFS:
- Use a queue to explore nodes level by level.
- Mark nodes visited when enqueued to avoid repeats.
- Track distance and parent for each node.
- After BFS, reconstruct path from target to source using parents.
- Guarantees shortest path in unweighted graphs.

Full Transcript

This visualization shows how BFS finds the shortest path in an unweighted graph. We start from the source node, add it to a queue, and mark it visited with distance zero. Then, we repeatedly dequeue a node, visit its neighbors, and enqueue unvisited neighbors while marking them visited, setting their distance as current node distance plus one, and recording their parent node. This process continues until the queue is empty, meaning all reachable nodes are processed. The parent array allows us to reconstruct the shortest path from any target node back to the source. Key points include marking nodes visited when enqueued to prevent duplicates and infinite loops, and that unreachable nodes remain with infinite distance and no parent. The execution table tracks each step, showing queue contents, visited nodes, distances, and parents, helping learners see the BFS progression clearly.

Practice

1. What does BFS (Breadth-First Search) help find in an unweighted graph?

easy

A. The total number of edges in the graph

B. The node with the highest degree

C. The longest path in the graph

D. The shortest path from a start node to all other nodes

Solution

1. Step 1: Understand BFS traversal

   BFS explores nodes level by level starting from the source node.

2. Step 2: BFS finds shortest paths in unweighted graphs

   Because BFS visits nodes in order of increasing distance, it finds shortest paths.

3. Final Answer:

   The shortest path from a start node to all other nodes -> Option D

4. Quick Check:

   BFS = Shortest path in unweighted graph [OK]

Hint: BFS explores neighbors level-wise to find shortest paths [OK]

Common Mistakes:

• Confusing BFS with DFS for shortest path
• Thinking BFS finds longest path
• Assuming BFS counts edges incorrectly

2. Which C# data structure is best to use as a queue for BFS implementation?

easy

A. Queue<T>

B. List<T>

C. Stack<T>

D. Dictionary

Solution

1. Step 1: Identify BFS traversal order

   BFS uses FIFO order to explore nodes level by level.

2. Step 2: Choose data structure matching FIFO

   Queue<T> provides FIFO behavior, perfect for BFS.

3. Final Answer:

   Queue<T> -> Option A

4. Quick Check:

   Queue = FIFO for BFS [OK]

Hint: Use Queue<T> for BFS to maintain correct node order [OK]

Common Mistakes:

• Using Stack<T> which is LIFO, wrong for BFS
• Using List<T> without queue behavior
• Confusing Dictionary with queue

3. What is the output distance array after running BFS from node 0 on this graph?

Graph edges:
0 - 1
0 - 2
1 - 3
2 - 3
3 - 4

Assume distance to start node 0 is 0 and unreachable nodes have distance -1.

medium

A. [0, 1, 1, 2, 3]

B. [0, 1, 2, 3, 4]

C. [0, 1, 1, 1, 2]

D. [0, -1, -1, -1, -1]

Solution

1. Step 1: Initialize distances and start BFS from node 0

   Distance[0] = 0; others = -1 initially.

2. Step 2: Visit neighbors level-wise

   From 0: nodes 1 and 2 get distance 1. From 1 and 2: node 3 gets distance 2. From 3: node 4 gets distance 3.

3. Final Answer:

   [0, 1, 1, 2, 3] -> Option A

4. Quick Check:

   Distances = [0,1,1,2,3] [OK]

Hint: Track distances level by level from start node [OK]

Common Mistakes:

• Assigning wrong distances to nodes
• Confusing BFS with DFS distances
• Not initializing unreachable nodes as -1

4. Identify the bug in this BFS shortest path code snippet in C#:

int[] dist = new int[n];
for (int i = 0; i < n; i++) dist[i] = -1;
Queue<int> q = new Queue<int>();
dist[start] = 0;
q.Enqueue(start);
while (q.Count > 0) {
  int u = q.Dequeue();
  foreach (int v in graph[u]) {
    if (dist[v] == 0) {
      dist[v] = dist[u] + 1;
      q.Enqueue(v);
    }
  }
}

medium

A. Enqueue should be done before setting dist[v]

B. Queue should be Stack for BFS

C. dist[v] == 0 should be dist[v] == -1 to check unvisited nodes

D. dist[start] should be -1 initially

Solution

1. Step 1: Understand distance initialization and visit check

   Distances start at -1 for unvisited nodes; 0 means visited or start node.

2. Step 2: Check condition for visiting neighbors

   Condition 'dist[v] == 0' wrongly treats unvisited nodes as visited; should be 'dist[v] == -1'.

3. Final Answer:

   dist[v] == -1 to check unvisited nodes -> Option C

4. Quick Check:

   Check unvisited with -1, not 0 [OK]

Hint: Use -1 to mark unvisited nodes in BFS distance array [OK]

Common Mistakes:

• Checking dist[v] == 0 instead of -1
• Using Stack instead of Queue for BFS
• Incorrect initial distance for start node

5. Given an unweighted graph with nodes 0 to 5 and edges:

0-1, 0-2, 1-3, 3-4, 4-5

What is the shortest path from node 0 to node 5 using BFS?

hard

A. [0, 2, 3, 4, 5]

B. [0, 1, 3, 4, 5]

C. [0, 1, 2, 3, 4, 5]

D. [0, 2, 4, 5]

Solution

1. Step 1: Run BFS from node 0 to find shortest distances

   Distances: 0(0), 1(1), 2(1), 3(2), 4(3), 5(4).

2. Step 2: Trace shortest path back from node 5

   From 5 to 4, 4 to 3, 3 to 1, 1 to 0: 0->1->3->4->5.

3. Final Answer:

   [0, 1, 3, 4, 5] -> Option B

4. Quick Check:

   Shortest path = [0,1,3,4,5] [OK]

Hint: Trace BFS parents backward to find shortest path [OK]

Common Mistakes:

• Attempting path via node 2 (no 2-3 edge)
• Skipping nodes in path
• Confusing BFS with DFS path