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

Shortest Path in Unweighted Graph Using BFS

📖 Scenario: You are working on a simple map application that shows the shortest route between places connected by roads. The roads have no distances, so the shortest path means the fewest roads to travel.We will represent the map as a graph where places are nodes and roads are edges. Your task is to find the shortest path from a starting place to all other places using a method called Breadth-First Search (BFS).

🎯 Goal: Build a C++ program that uses BFS to find the shortest number of roads from a starting place to every other place in the map. You will create the graph, set the starting place, run BFS, and print the shortest distances.

📋 What You'll Learn

Create an adjacency list to represent the graph with 5 nodes (0 to 4) and these edges: (0-1), (0-2), (1-2), (1-3), (2-4)

Create a variable start with value 0 as the starting node

Implement BFS using a queue to find shortest distances from start to all nodes

Print the shortest distances array after BFS completes

💡 Why This Matters

🌍 Real World

Finding shortest routes in maps, social networks, or any system where connections have equal cost.

💼 Career

Understanding BFS and shortest path algorithms is fundamental for software engineers working in areas like navigation apps, network routing, and game development.

1

Create the Graph as an Adjacency List

Create a vector of vectors of integers called graph with size 5. Add edges to represent these connections: 0 connected to 1 and 2, 1 connected to 0, 2, and 3, 2 connected to 0, 1, and 4, 3 connected to 1, and 4 connected to 2.

DSA C++

# Create the graph adjacency list with 5 nodes
# Your code here

Hint

Use vector> graph(5); to create the graph. Then assign neighbors for each node using graph[index] = {neighbors};.

2

Set the Starting Node

Create an integer variable called start and set it to 0. This will be the node where BFS begins.

DSA C++

#include 
#include 
#include 

using namespace std;

int main() {
    vector> graph(5);
    graph[0] = {1, 2};
    graph[1] = {0, 2, 3};
    graph[2] = {0, 1, 4};
    graph[3] = {1};
    graph[4] = {2};

    // Set the starting node
    # Your code here

    return 0;
}

Hint

Simply write int start = 0; to set the starting node.

3

Implement BFS to Find Shortest Distances

Create a vector of integers called distance with size 5, initialized with -1. Set distance[start] to 0. Use a queue of integers called q. Push start into q. While q is not empty, pop the front node into current. For each neighbor in graph[current], if distance[neighbor] is -1, set distance[neighbor] to distance[current] + 1 and push neighbor into q. This finds shortest paths from start.

DSA C++

#include 
#include 
#include 

using namespace std;

int main() {
    vector> graph(5);
    graph[0] = {1, 2};
    graph[1] = {0, 2, 3};
    graph[2] = {0, 1, 4};
    graph[3] = {1};
    graph[4] = {2};

    int start = 0;

    // Implement BFS to find shortest distances
    # Your code here

    return 0;
}

Hint

Use a queue to explore nodes level by level. Mark distances as you go. Initialize all distances to -1, then set the start node distance to 0.

4

Print the Shortest Distances

Use a for loop with variable i from 0 to 4 to print the shortest distance to each node in the format: Distance to node i: distance[i].

DSA C++

Hint

Use a for loop from 0 to 4 and print each distance with cout.

Practice

1. What is the main purpose of using BFS (Breadth-First Search) in an unweighted graph?

easy

A. To sort the nodes in topological order

B. To find the maximum depth of the graph

C. To find the shortest path from a source node to all other nodes

D. To detect cycles in the graph

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 from source to all nodes.

3. Final Answer:

   To find the shortest path from a source node to all other nodes -> Option C

4. Quick Check:

   BFS shortest path = D [OK]

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

Common Mistakes:

• Confusing BFS with DFS for shortest path
• Thinking BFS finds maximum depth
• Assuming BFS sorts nodes topologically

2. Which of the following is the correct way to initialize a queue for BFS in C++?

easy

A. queue<int> q; q.push(0);

B. stack<int> q; q.push(0);

C. queue<int> q; q.insert(0);

D. queue<int> q; q.add(0);

Solution

1. Step 1: Identify correct queue declaration

   In C++, BFS uses std::queue with push() to add elements.

2. Step 2: Check method names

   push() is correct for queue; insert() and add() are invalid; stack is wrong data structure.

3. Final Answer:

   queue<int> q; q.push(0); -> Option A

4. Quick Check:

   queue push() method = C [OK]

Hint: Use std::queue and push() to add elements in BFS [OK]

Common Mistakes:

• Using stack instead of queue
• Using insert() or add() instead of push()
• Confusing queue methods with vector methods

3. Consider the following C++ code snippet for BFS shortest path in an unweighted graph:

int n = 4;
vector adj = {{1,2}, {0,2,3}, {0,1,3}, {1,2}};
vector<int> dist(n, -1);
queue<int> q;
dist[0] = 0;
q.push(0);
while(!q.empty()) {
  int u = q.front(); q.pop();
  for(int v : adj[u]) {
    if(dist[v] == -1) {
      dist[v] = dist[u] + 1;
      q.push(v);
    }
  }
}
for(int i=0; iWhat is the output?

medium

A. 0 1 1 2

B. 0 1 2 3

C. 0 2 1 1

D. 0 1 1 1

Solution

1. Step 1: Initialize distances and start BFS

   dist[0]=0, others -1; start from node 0.

2. Step 2: BFS visits neighbors and updates distances

   From 0: neighbors 1,2 get dist=1; from 1 and 2: neighbor 3 gets dist=2.

3. Final Answer:

   0 1 1 2 -> Option A

4. Quick Check:

   BFS distance array = 0 1 1 2 [OK]

Hint: BFS distance increments by 1 per level from source [OK]

Common Mistakes:

• Mixing up node indices and distances
• Not initializing distances to -1
• Forgetting to check if node was visited

4. The following BFS code snippet is intended to find shortest paths in an unweighted graph. Identify the bug:

int n = 3;
vector adj = {{1}, {0,2}, {1}};
vector<int> dist(n, 0);
queue<int> q;
dist[0] = 0;
q.push(0);
while(!q.empty()) {
  int u = q.front(); q.pop();
  for(int v : adj[u]) {
    if(dist[v] == 0) {
      dist[v] = dist[u] + 1;
      q.push(v);
    }
  }
}
for(int i=0; i

medium

A. dist[u] is not updated inside the loop

B. Queue is not used properly

C. Adjacency list is incorrect

D. dist vector initialized with 0 instead of -1

Solution

1. Step 1: Check distance initialization

   dist initialized with 0 means unvisited nodes are indistinguishable from source.

2. Step 2: Identify impact on BFS logic

   Condition dist[v] == 0 fails to detect unvisited nodes correctly, causing wrong or no updates.

3. Final Answer:

   dist vector initialized with 0 instead of -1 -> Option D

4. Quick Check:

   dist init must be -1 to mark unvisited [OK]

Hint: Initialize distances with -1 to mark unvisited nodes [OK]

Common Mistakes:

• Using 0 as unvisited marker
• Not checking visited condition properly
• Misusing queue operations

5. You have an unweighted graph with 5 nodes and edges: 0-1, 0-2, 1-3, 2-3, 3-4. Using BFS from node 0, what is the shortest path distance to node 4? Also, which nodes are on one shortest path from 0 to 4?

hard

A. Distance: 2; Path: 0 -> 1 -> 3 -> 4

B. Distance: 3; Path: 0 -> 2 -> 3 -> 4

C. Distance: 2; Path: 0 -> 3 -> 4

D. Distance: 4; Path: 0 -> 2 -> 3 -> 4

Solution

1. Step 1: Build graph and run BFS from node 0

   Edges: 0-1,0-2; 1-3; 2-3; 3-4. BFS levels: 0(dist=0), 1 and 2(dist=1), 3(dist=2), 4(dist=3).

2. Step 2: Identify shortest path to node 4

   Shortest distance to 4 is 3. Paths: 0->1->3->4 or 0->2->3->4. Distance: 3; Path: 0 -> 2 -> 3 -> 4 shows correct distance and one valid path.

3. Final Answer:

   Distance: 3; Path: 0 -> 2 -> 3 -> 4 -> Option B

4. Quick Check:

   Shortest path length = 3 via node 2 [OK]

Hint: Trace BFS levels to find shortest path and distance [OK]

Common Mistakes:

• Assuming direct edge from 0 to 3
• Confusing distance with number of edges
• Ignoring multiple shortest paths