Shortest Path in Unweighted Graph Using BFS in DSA C# - Build from Scratch

Shortest Path in Unweighted Graph Using BFS

📖 Scenario: Imagine you are navigating a city map represented as a graph. Each intersection is a node, and roads between intersections are edges. You want to find the shortest number of roads to travel from one intersection to another.

🎯 Goal: Build a program that finds the shortest path length between two nodes in an unweighted graph using Breadth-First Search (BFS).

📋 What You'll Learn

Create a graph using an adjacency list representation with exact nodes and edges.

Add variables to store the start and target nodes for the path search.

Implement BFS to find the shortest path length from start to target node.

Print the shortest path length or -1 if no path exists.

💡 Why This Matters

🌍 Real World

Finding shortest routes in maps, social networks, or network routing where all edges have equal cost.

💼 Career

Understanding BFS and shortest path algorithms is essential for software engineers working on navigation, networking, and graph-based problem solving.

1

Create the Graph as an Adjacency List

Create a dictionary called graph representing the graph adjacency list with these exact entries: 1: new List {2, 3}, 2: new List {1, 4}, 3: new List {1, 4, 5}, 4: new List {2, 3, 5}, 5: new List {3, 4}.

DSA C#

// Your code here

Hint

Use a Dictionary<int, List<int>> to represent the graph adjacency list.

2

Add Start and Target Nodes

Add two integer variables called start and target and set them to 1 and 5 respectively.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary> graph = new Dictionary>
        {
            {1, new List {2, 3}},
            {2, new List {1, 4}},
            {3, new List {1, 4, 5}},
            {4, new List {2, 3, 5}},
            {5, new List {3, 4}}
        };
        // Your code here
    }
}

Hint

Declare int start = 1; and int target = 5; inside Main.

3

Implement BFS to Find Shortest Path Length

Implement BFS using a queue to find the shortest path length from start to target. Create a dictionary called distance to store distances, initialize distance[start] to 0, and use a Queue<int> called queue. Use a while loop to process nodes until queue is empty or target is found. Update distances for neighbors not yet visited.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary> graph = new Dictionary>
        {
            {1, new List {2, 3}},
            {2, new List {1, 4}},
            {3, new List {1, 4, 5}},
            {4, new List {2, 3, 5}},
            {5, new List {3, 4}}
        };

        int start = 1;
        int target = 5;

        // Implement BFS here
    }
}

Hint

Use a Dictionary<int, int> for distances and a Queue<int> for BFS traversal.

4

Print the Shortest Path Length

Print the shortest path length from start to target by printing distance[target]. If distance[target] is -1, it means no path exists.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary> graph = new Dictionary>
        {
            {1, new List {2, 3}},
            {2, new List {1, 4}},
            {3, new List {1, 4, 5}},
            {4, new List {2, 3, 5}},
            {5, new List {3, 4}}
        };

        int start = 1;
        int target = 5;

        Dictionary distance = new Dictionary();
        foreach (var node in graph.Keys)
        {
            distance[node] = -1;
        }
        distance[start] = 0;

        Queue queue = new Queue();
        queue.Enqueue(start);

        while (queue.Count > 0)
        {
            int current = queue.Dequeue();
            if (current == target)
            {
                break;
            }

            foreach (int neighbor in graph[current])
            {
                if (distance[neighbor] == -1)
                {
                    distance[neighbor] = distance[current] + 1;
                    queue.Enqueue(neighbor);
                }
            }
        }

        // Print the shortest path length
    }
}

Hint

Use Console.WriteLine(distance[target]); to print the shortest path length.

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