Shortest Path in Unweighted Graph Using BFS in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does BFS stand for and what is its main use in graphs?

BFS stands for Breadth-First Search. It is mainly used to explore all nodes of a graph level by level and find the shortest path in an unweighted graph.

beginner

Why is BFS suitable for finding the shortest path in an unweighted graph?

Because BFS explores nodes in order of their distance from the start node, the first time it reaches a node, it has found the shortest path to that node.

beginner

In BFS for shortest path, what data structure is used to keep track of nodes to visit next?

A queue is used to keep track of nodes to visit next, ensuring nodes are processed in the order they are discovered.

intermediate

What additional information do we store during BFS to reconstruct the shortest path?

We store the parent (or predecessor) of each node, so after BFS finishes, we can trace back from the target node to the start node to get the path.

intermediate

What is the time complexity of BFS when finding the shortest path in an unweighted graph?

The time complexity is O(V + E), where V is the number of vertices and E is the number of edges, because each node and edge is processed at most once.

What data structure does BFS use to explore nodes in order?

A Queue

B Stack

C Priority Queue

D HashSet

BFS uses a queue to explore nodes level by level.

In an unweighted graph, BFS finds the shortest path because it:

A Uses weights to calculate distance

B Explores nodes randomly

C Explores nodes in increasing order of distance from the start

D Uses recursion to find paths

BFS explores nodes level by level, so the first time it reaches a node, it has found the shortest path.

Which of these is NOT needed to reconstruct the shortest path after BFS?

A Stack to store all nodes in the graph

B Parent array to track predecessors

C Visited set to avoid revisiting nodes

D Distance array to track steps from start

A stack of all nodes is not needed; parent and visited information suffice.

What is the initial step in BFS for shortest path?

A Mark all nodes as visited

B Add all nodes to the queue

C Calculate weights of edges

D Add the start node to the queue and mark it visited

BFS starts by adding the start node to the queue and marking it visited.

What is the time complexity of BFS in terms of vertices (V) and edges (E)?

A O(log V)

B O(V + E)

C O(E^2)

D O(V^2)

BFS visits each vertex and edge once, so time complexity is O(V + E).

Explain step-by-step how BFS finds the shortest path in an unweighted graph.

Think about how BFS explores nodes and how to remember the path.

Describe how you would implement BFS in C# to find the shortest path and print it.

Focus on data structures and the order of operations.

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