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

Shortest Path in Unweighted Graph Using BFS

📖 Scenario: Imagine you are helping a friend find the shortest route between two places on a simple map. The map is like a network of connected points (places), and you want to find the quickest way to get from one point to another without any weights or distances, just connections.

🎯 Goal: You will build a program in C that finds the shortest path between two points in an unweighted graph using Breadth-First Search (BFS). The program will show the path as a sequence of nodes.

📋 What You'll Learn

Create an adjacency list to represent the graph with 6 nodes (0 to 5) and specific edges

Add variables to store the start node and end node for the path search

Implement BFS to find the shortest path from start node to end node

Print the shortest path as a sequence of nodes separated by arrows

💡 Why This Matters

🌍 Real World

Finding shortest routes in maps, social networks, or any system where connections have no weights.

💼 Career

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

1

Create the Graph Using an Adjacency List

Create an adjacency list called graph as an array of 6 integer arrays with these exact edges:
0 connected to 1 and 2,
1 connected to 0 and 3,
2 connected to 0 and 3 and 4,
3 connected to 1 and 2 and 5,
4 connected to 2 and 5,
5 connected to 3 and 4.
Use arrays and sizes to represent neighbors for each node.

DSA C

// Your code here to create the graph adjacency list

Hint

Use a 2D array for graph and an array graph_sizes to store how many neighbors each node has. Use -1 to fill unused slots.

2

Set Start and End Nodes for the Path Search

Create two integer variables called start and end and set start = 0 and end = 5 to find the shortest path from node 0 to node 5.

DSA C

#include 

int graph[6][3] = {
    {1, 2, -1},    // neighbors of node 0
    {0, 3, -1},    // neighbors of node 1
    {0, 3, 4},     // neighbors of node 2
    {1, 2, 5},     // neighbors of node 3
    {2, 5, -1},    // neighbors of node 4
    {3, 4, -1}     // neighbors of node 5
};

int graph_sizes[6] = {2, 2, 3, 3, 2, 2};

// Your code here to set start and end nodes

Hint

Just create two integer variables start and end and assign the values 0 and 5 respectively.

3

Implement BFS to Find the Shortest Path

Write a function called bfs_shortest_path that takes start, end, graph, and graph_sizes as inputs and finds the shortest path using BFS. Use arrays visited, queue, and parent to track visited nodes, BFS queue, and parents for path reconstruction. Fill parent with -1 initially. The function should fill a global array path with the nodes in the shortest path from start to end and return the length of the path. Use a queue with front and rear indices for BFS.

DSA C

#include 

int graph[6][3] = {
    {1, 2, -1},    // neighbors of node 0
    {0, 3, -1},    // neighbors of node 1
    {0, 3, 4},     // neighbors of node 2
    {1, 2, 5},     // neighbors of node 3
    {2, 5, -1},    // neighbors of node 4
    {3, 4, -1}     // neighbors of node 5
};

int graph_sizes[6] = {2, 2, 3, 3, 2, 2};

int start = 0;
int end = 5;

// Your code here to implement bfs_shortest_path function

Hint

Use BFS with a queue to visit nodes level by level. Keep track of parents to rebuild the path after reaching the end node. Reverse the path array before returning.

4

Print the Shortest Path

Call the bfs_shortest_path function with start, end, graph, and graph_sizes. Store the returned length in path_length. Then print the shortest path nodes from path[0] to path[path_length - 1] separated by arrows ->. For example: 0 -> 2 -> 4 -> 5

DSA C

#include 

int graph[6][3] = {
    {1, 2, -1},    // neighbors of node 0
    {0, 3, -1},    // neighbors of node 1
    {0, 3, 4},     // neighbors of node 2
    {1, 2, 5},     // neighbors of node 3
    {2, 5, -1},    // neighbors of node 4
    {3, 4, -1}     // neighbors of node 5
};

int graph_sizes[6] = {2, 2, 3, 3, 2, 2};

int start = 0;
int end = 5;

int path[6];

int bfs_shortest_path(int start, int end, int graph[6][3], int graph_sizes[6]) {
    int visited[6] = {0};
    int parent[6];
    for (int i = 0; i < 6; i++) {
        parent[i] = -1;
    }

    int queue[6];
    int front = 0, rear = 0;

    visited[start] = 1;
    queue[rear++] = start;

    while (front < rear) {
        int current = queue[front++];
        if (current == end) {
            break;
        }
        for (int i = 0; i < graph_sizes[current]; i++) {
            int neighbor = graph[current][i];
            if (!visited[neighbor]) {
                visited[neighbor] = 1;
                parent[neighbor] = current;
                queue[rear++] = neighbor;
            }
        }
    }

    // Reconstruct path
    int length = 0;
    int crawl = end;
    while (crawl != -1) {
        path[length++] = crawl;
        crawl = parent[crawl];
    }

    // Reverse path
    for (int i = 0; i < length / 2; i++) {
        int temp = path[i];
        path[i] = path[length - i - 1];
        path[length - i - 1] = temp;
    }

    return length;
}

// Your code here to call bfs_shortest_path and print the path

Hint

Call the BFS function, get the path length, then print each node in the path separated by arrows. End with a newline.

Practice

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

easy

A. The total number of nodes in the graph

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

C. The longest path between two nodes

D. The heaviest edge in the graph

Solution

1. Step 1: Understand BFS traversal

   BFS explores nodes level by level starting from the source node, visiting all neighbors before moving deeper.

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

   Because BFS visits nodes in order of increasing distance, it finds the shortest path in terms of edges from the start node.

3. Final Answer:

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

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 works only for weighted graphs

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

easy

A. int queue[MAX]; int front = 0, rear = 0;

B. queue<int> q; // C++ syntax

C. Queue q = new Queue(); // Java syntax

D. var q = []; // JavaScript syntax

Solution

1. Step 1: Identify C syntax for queue

   C does not have built-in queue; we use arrays with front and rear indices to simulate queue.

2. Step 2: Check options for C correctness

   int queue[MAX]; int front = 0, rear = 0; uses array and indices, which is valid in C. Others use non-C syntax.

3. Final Answer:

   int queue[MAX]; int front = 0, rear = 0; -> Option A

4. Quick Check:

   C queue uses array + front/rear indices [OK]

Hint: Use array with front/rear for queue in C [OK]

Common Mistakes:

• Using C++ or Java syntax in C code
• Not initializing front and rear indices
• Assuming queue is built-in in C

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 nodes are 0 to 4 and distance to unreachable nodes is -1.

medium

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

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

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

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

Solution

1. Step 1: Start BFS from node 0 and set distance[0] = 0

   Initialize distances: distance[0]=0, others = -1.

2. Step 2: Visit neighbors level-wise

   Neighbors of 0: 1 and 2 get distance 1. Then neighbors of 1 and 2: node 3 gets distance 2. Finally, neighbor of 3: node 4 gets distance 3.

3. Final Answer:

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

4. Quick Check:

   Distances increase by 1 per BFS level [OK]

Hint: Distance increments by 1 each BFS level from start [OK]

Common Mistakes:

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

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

void bfs(int start) {
  queue[rear++] = start;
  visited[start] = 1;
  distance[start] = 0;
  while(front < rear) {
    int u = queue[front++];
    for(int v : adj[u]) {
      if(!visited[v]) {
        visited[v] = 1;
        distance[v] = distance[u] + 1;
        queue[rear++] = v;
      }
    }
  }
}

medium

A. Not marking start node as visited

B. Not initializing distance array before BFS

C. Queue overflow not handled

D. Using 'int v : adj[u]' is invalid in C

Solution

1. Step 1: Check syntax of for loop in C

   Range-based for loops like 'for(int v : adj[u])' are not valid in C; this is C++ syntax.

2. Step 2: Identify correct iteration method in C

   In C, adjacency lists require explicit indexing or pointer iteration, not range-based loops.

3. Final Answer:

   Using 'int v : adj[u]' is invalid in C -> Option D

4. Quick Check:

   Range-based for loops = invalid in C [OK]

Hint: C uses indexed loops, not range-based for [OK]

Common Mistakes:

• Using C++ syntax in C code
• Ignoring queue overflow possibility
• Forgetting to initialize arrays

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

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

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

hard

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

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

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

D. [0, 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). BFS visits neighbors level-wise.

2. Step 2: Trace shortest path from 5 back to 0

   From 5 to 4, 4 to 3, 3 to 1 (via 1-3 edge; no 2-3 edge), 1 to 0.

3. Final Answer:

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

4. Quick Check:

   Shortest path = BFS parent chain [OK]

Hint: Trace BFS parents backward for shortest path [OK]

Common Mistakes:

• Choosing longer paths ignoring BFS order
• Assuming direct edge from 0 to 5
• Confusing BFS with DFS path