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 to find the shortest way out. Your shout reaches all nearby friends first, then their friends, spreading out evenly until someone finds the exit.

Graph adjacency list:
0 -> 1 -> 2 -> null
1 -> 0 -> 3 -> null
2 -> 0 -> 3 -> null
3 -> 1 -> 2 -> 4 -> null
4 -> 3 -> null
Start: 0
Goal: shortest path to 4

Dry Run Walkthrough

Input: Graph edges: 0-1, 0-2, 1-3, 2-3, 3-4; Find shortest path from 0 to 4

Goal: Find the shortest number of edges from node 0 to node 4

Step 1: Start BFS from node 0, mark distance[0] = 0, enqueue 0

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

Why: We begin from the start node with distance zero

Step 2: Dequeue 0, visit neighbors 1 and 2, set distance=1, enqueue them

Queue: [1, 2]
Distances: 0=0, 1=1, 2=1, others=∞

Why: Neighbors of 0 are one step away

Step 3: Dequeue 1, visit neighbor 3, set distance=2, enqueue 3

Queue: [2, 3]
Distances: 0=0, 1=1, 2=1, 3=2, 4=∞

Why: 3 is two steps from 0 via 1

Step 4: Dequeue 2, visit neighbor 3 but already visited with distance 2, skip

Queue: [3]
Distances unchanged

Why: We do not update distance if already found shorter or equal path

Step 5: Dequeue 3, visit neighbor 4, set distance=3, enqueue 4

Queue: [4]
Distances: 0=0, 1=1, 2=1, 3=2, 4=3

Why: 4 is three steps from 0 via 3

Step 6: Dequeue 4, goal reached, stop BFS

Queue: []
Distances final

Why: We found shortest path to target node

Result:

Shortest distance from 0 to 4 is 3

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#define MAX 5

// Node for adjacency list
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

// Graph structure
typedef struct Graph {
    Node* adjLists[MAX];
    int visited[MAX];
    int distance[MAX];
} Graph;

// Create node
Node* createNode(int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// Initialize graph
void initGraph(Graph* graph) {
    for (int i = 0; i < MAX; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
        graph->distance[i] = -1; // -1 means unvisited
    }
}

// Add edge
void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// BFS to find shortest path distance
void bfsShortestPath(Graph* graph, int start, int target) {
    int queue[MAX];
    int front = 0, rear = 0;

    graph->visited[start] = 1;
    graph->distance[start] = 0;
    queue[rear++] = start;

    while (front < rear) {
        int current = queue[front++]; // dequeue

        if (current == target) {
            break; // reached target
        }

        Node* temp = graph->adjLists[current];
        while (temp) {
            int adjVertex = temp->vertex;
            if (!graph->visited[adjVertex]) {
                graph->visited[adjVertex] = 1;
                graph->distance[adjVertex] = graph->distance[current] + 1;
                queue[rear++] = adjVertex; // enqueue
            }
            temp = temp->next;
        }
    }

    printf("Shortest distance from %d to %d is %d\n", start, target, graph->distance[target]);
}

int main() {
    Graph graph;
    initGraph(&graph);

    addEdge(&graph, 0, 1);
    addEdge(&graph, 0, 2);
    addEdge(&graph, 1, 3);
    addEdge(&graph, 2, 3);
    addEdge(&graph, 3, 4);

    bfsShortestPath(&graph, 0, 4);

    return 0;
}

graph->visited[start] = 1; graph->distance[start] = 0; queue[rear++] = start;

Initialize BFS from start node with distance zero and enqueue it

int current = queue[front++];

Dequeue current node to explore neighbors

if (current == target) { break; }

Stop BFS when target node is reached

while (temp) { int adjVertex = temp->vertex; if (!graph->visited[adjVertex]) { graph->visited[adjVertex] = 1; graph->distance[adjVertex] = graph->distance[current] + 1; queue[rear++] = adjVertex; } temp = temp->next; }

Visit all unvisited neighbors, update distance, and enqueue them

printf("Shortest distance from %d to %d is %d\n", start, target, graph->distance[target]);

Print the shortest distance found

Output

Shortest distance from 0 to 4 is 3

Complexity Analysis

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

Space: O(V) for queue, visited, and distance arrays

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

Edge Cases

Start equals target

Distance is zero immediately

DSA C

if (current == target) { break; }

No path exists between start and target

Distance remains -1 indicating unreachable

DSA C

graph->distance[target] initialized to -1 and unchanged if unreachable

Graph with isolated nodes

Isolated nodes remain unvisited with distance -1

DSA C

visited array check before enqueueing neighbors

When to Use This Pattern

When asked for shortest path in an unweighted graph, use BFS because it explores nodes in layers ensuring the shortest path is found first.

Common Mistakes

Mistake: Not marking nodes as visited before enqueueing causes repeated visits and infinite loops
Fix: Mark nodes visited immediately when enqueueing to avoid revisiting

Summary

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

Use when you need the minimum number of edges between two nodes in an unweighted graph.

BFS explores neighbors level by level, guaranteeing shortest path discovery.

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