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.