Shortest Path in Unweighted Graph Using BFS in DSA C#

Mental Model

We find the shortest path by exploring neighbors level by level, like ripples spreading in water.

Analogy: Imagine you are in a maze and shout out loud. The sound reaches rooms closest to you first, then rooms farther away. The first time the sound reaches a room is the shortest path to it.

Graph nodes connected by edges:
  A -> B -> C
  ↓    ↓
  D -> E
Start at A, explore neighbors B and D first, then their neighbors.

Dry Run Walkthrough

Input: Graph edges: A-B, A-D, B-C, B-E, D-E; Find shortest path from A to E

Goal: Find the shortest path from node A to node E using BFS

Step 1: Start BFS from A, mark A distance 0

Queue: [A]
Distances: A=0, others=∞

Why: We begin from the start node with distance zero

Step 2: Dequeue A, enqueue neighbors B and D with distance 1

Queue: [B, D]
Distances: A=0, B=1, D=1, others=∞

Why: Neighbors of A are one step away

Step 3: Dequeue B, enqueue neighbors C and E with distance 2

Queue: [D, C, E]
Distances: A=0, B=1, D=1, C=2, E=2

Why: Neighbors of B are two steps from A

Step 4: Dequeue D, neighbor E already visited, skip

Queue: [C, E]
Distances unchanged

Why: E already has shortest distance, no update needed

Step 5: Dequeue C, no new neighbors

Queue: [E]
Distances unchanged

Why: No new nodes to explore from C

Step 6: Dequeue E, target found with distance 2

Queue: []
Distances unchanged

Why: Reached target node E with shortest path length 2

Result:

Shortest path distance from A to E is 2

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    private readonly Dictionary<string, List<string>> adj = new();

    public void AddEdge(string u, string v) {
        if (!adj.ContainsKey(u)) adj[u] = new List<string>();
        if (!adj.ContainsKey(v)) adj[v] = new List<string>();
        adj[u].Add(v);
        adj[v].Add(u); // undirected graph
    }

    public int ShortestPathBFS(string start, string target) {
        if (start == target) return 0;

        var queue = new Queue<string>();
        var distances = new Dictionary<string, int>();

        queue.Enqueue(start);
        distances[start] = 0; // start node distance 0

        while (queue.Count > 0) {
            var current = queue.Dequeue(); // dequeue current node
            foreach (var neighbor in adj[current]) {
                if (!distances.ContainsKey(neighbor)) {
                    distances[neighbor] = distances[current] + 1; // update distance
                    if (neighbor == target) return distances[neighbor]; // found target
                    queue.Enqueue(neighbor); // enqueue neighbor
                }
            }
        }
        return -1; // target not reachable
    }
}

class Program {
    static void Main() {
        var graph = new Graph();
        graph.AddEdge("A", "B");
        graph.AddEdge("A", "D");
        graph.AddEdge("B", "C");
        graph.AddEdge("B", "E");
        graph.AddEdge("D", "E");

        int distance = graph.ShortestPathBFS("A", "E");
        Console.WriteLine($"Shortest path distance from A to E is {distance}");
    }
}

queue.Enqueue(start); distances[start] = 0; // start node distance 0

Initialize BFS queue and set start node distance to zero

var current = queue.Dequeue(); // dequeue current node

Process nodes in FIFO order to explore neighbors level by level

if (!distances.ContainsKey(neighbor)) { distances[neighbor] = distances[current] + 1; // update distance queue.Enqueue(neighbor); // enqueue neighbor }

Visit unvisited neighbors, update their distance, and enqueue them

if (neighbor == target) return distances[neighbor]; // found target

Stop search immediately when target is found to get shortest path

Output

Shortest path distance from A to E is 2

Complexity Analysis

Time: O(V + E) because BFS visits each vertex and edge once

Space: O(V) for the queue and distance dictionary storing all vertices

vs Alternative: Compared to DFS which may explore longer paths first, BFS guarantees shortest path in unweighted graphs efficiently

Edge Cases

Start node equals target node

Returns distance 0 immediately

DSA C#

if (start == target) return 0;

Target node not reachable from start

Returns -1 indicating no path found

DSA C#

return -1; // target not reachable

Graph with isolated nodes

Only reachable nodes get distances, unreachable remain unvisited

DSA C#

if (!distances.ContainsKey(neighbor)) { ... }

When to Use This Pattern

When asked to find shortest paths in an unweighted graph, use BFS because it explores nodes in order of increasing distance.

Common Mistakes

Mistake: Using DFS instead of BFS, which does not guarantee shortest path in unweighted graphs
Fix: Use BFS to explore neighbors level by level to find shortest path

Mistake: Not marking visited nodes, causing infinite loops or repeated processing
Fix: Track visited nodes using a distance or visited set to avoid revisiting

Summary

Finds shortest path distance in an unweighted graph using BFS traversal.

Use when you need shortest path length between nodes in graphs without edge weights.

BFS explores neighbors level by level, ensuring the first time you reach a node is via the shortest path.

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