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.