BFS Breadth First Search on Graph in DSA C - Build from Scratch

BFS Breadth First Search on Graph

📖 Scenario: Imagine you have a map of cities connected by roads. You want to visit all cities starting from one city, exploring neighbors first before going deeper. This is like spreading out from your starting city to nearby cities, then their neighbors, and so on.

🎯 Goal: You will build a program in C that performs a Breadth First Search (BFS) on a graph represented by an adjacency list. The program will start from a given city (node) and print the order in which cities are visited.

📋 What You'll Learn

Create an adjacency list for a graph with 5 nodes (cities).

Create a queue to help with BFS traversal.

Implement BFS function to visit nodes in breadth-first order.

Print the order of nodes visited by BFS.

💡 Why This Matters

🌍 Real World

BFS is used in social networks to find friends nearby, in GPS apps to find shortest routes, and in web crawlers to explore websites layer by layer.

💼 Career

Understanding BFS is essential for software engineers working on search algorithms, network analysis, and AI pathfinding.

1

Create the Graph as an Adjacency List

Create an integer array called graph of size 5, where each element is a pointer to an integer array representing neighbors. Also create an integer array called graph_sizes of size 5 that stores the number of neighbors for each node. Initialize the graph with these exact neighbors:
Node 0: neighbors 1, 2
Node 1: neighbors 0, 3
Node 2: neighbors 0, 4
Node 3: neighbor 1
Node 4: neighbor 2

DSA C

#include 
#include 

int main() {
    // Create adjacency list arrays for graph
    // Your code here

    return 0;
}

Hint

Use arrays to store neighbors for each node. Then create an array of pointers graph to these neighbor arrays. Also create graph_sizes to store how many neighbors each node has.

2

Create a Queue for BFS

Create an integer array called queue of size 10 to hold nodes during BFS. Create two integer variables called front and rear and initialize both to 0. Create an integer array called visited of size 5 and initialize all elements to 0.

DSA C

#include 
#include 

int main() {
    int neighbors0[] = {1, 2};
    int neighbors1[] = {0, 3};
    int neighbors2[] = {0, 4};
    int neighbors3[] = {1};
    int neighbors4[] = {2};

    int* graph[5] = {neighbors0, neighbors1, neighbors2, neighbors3, neighbors4};
    int graph_sizes[5] = {2, 2, 2, 1, 1};

    // Create queue and visited array
    // Your code here

    return 0;
}

Hint

Use an array queue to hold nodes to visit. Use front and rear to track queue positions. Use visited to mark nodes already visited.

3

Implement BFS Traversal

Write code to perform BFS starting from node 0. Mark node 0 as visited and add it to the queue. While the queue is not empty (check front != rear), remove the front node from the queue, print it, then add all its unvisited neighbors to the queue and mark them visited.

DSA C

#include 
#include 

int main() {
    int neighbors0[] = {1, 2};
    int neighbors1[] = {0, 3};
    int neighbors2[] = {0, 4};
    int neighbors3[] = {1};
    int neighbors4[] = {2};

    int* graph[5] = {neighbors0, neighbors1, neighbors2, neighbors3, neighbors4};
    int graph_sizes[5] = {2, 2, 2, 1, 1};

    int queue[10];
    int front = 0;
    int rear = 0;
    int visited[5] = {0};

    // Write BFS starting from node 0
    // Your code here

    return 0;
}

Hint

Start BFS by marking node 0 visited and adding it to queue. Then loop while queue not empty, remove front node, print it, and add unvisited neighbors to queue.

4

Print BFS Result

Add a newline print statement after the BFS loop to print the visited order clearly.

DSA C

#include 
#include 

int main() {
    int neighbors0[] = {1, 2};
    int neighbors1[] = {0, 3};
    int neighbors2[] = {0, 4};
    int neighbors3[] = {1};
    int neighbors4[] = {2};

    int* graph[5] = {neighbors0, neighbors1, neighbors2, neighbors3, neighbors4};
    int graph_sizes[5] = {2, 2, 2, 1, 1};

    int queue[10];
    int front = 0;
    int rear = 0;
    int visited[5] = {0};

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

    while (front != rear) {
        int current = queue[front++];
        printf("%d ", current);

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

    // Print a newline character
    // Your code here

    return 0;
}

Hint

After printing all nodes in BFS order, print a newline using printf("\n"); to end the output cleanly.