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.

Practice

1. What does BFS (Breadth First Search) primarily use to keep track of nodes to visit next in a graph?

easy

A. A queue to explore nodes level by level

B. A stack to explore nodes deeply first

C. A hash map to store visited nodes only

D. A priority queue to explore nodes by weight

Solution

1. Step 1: Understand BFS traversal method

   BFS explores nodes in layers, visiting all neighbors before going deeper.

2. Step 2: Identify the data structure used

   To achieve level-by-level traversal, BFS uses a queue to store nodes to visit next.

3. Final Answer:

   A queue to explore nodes level by level -> Option A

4. Quick Check:

   BFS uses queue = A [OK]

Hint: BFS uses a queue, DFS uses a stack [OK]

Common Mistakes:

• Confusing BFS with DFS and choosing stack
• Thinking BFS uses priority queue for weights
• Ignoring the need for a data structure to track nodes

2. Which of the following is the correct way to enqueue a node `v` in a BFS implementation using C?

easy

A. queue.push(v);

B. queue.insert(v);

C. queue.add(v);

D. enqueue(queue, v);

Solution

1. Step 1: Recognize C queue operation syntax

   In C, queues are usually implemented with functions like enqueue(queue, value).

2. Step 2: Identify correct enqueue function call

   queue.push and queue.add are not standard C; enqueue(queue, v) is typical.

3. Final Answer:

   enqueue(queue, v); -> Option D

4. Quick Check:

   Use enqueue(queue, v) in C [OK]

Hint: C uses enqueue(queue, value) for queues [OK]

Common Mistakes:

• Using push or add which are not C queue functions
• Confusing queue insertion with array insertion
• Using incorrect method names from other languages

3. Consider the following graph represented as adjacency list:

0: 1, 2
1: 0, 3
2: 0, 3
3: 1, 2

If BFS starts from node 0, what is the order of nodes visited?

medium

A. [0, 2, 1, 3]

B. [0, 1, 2, 3]

C. [0, 3, 1, 2]

D. [0, 1, 3, 2]

Solution

1. Step 1: Start BFS from node 0

   Visit 0, enqueue neighbors 1 and 2.

2. Step 2: Visit nodes in queue order

   Dequeue 1, enqueue its unvisited neighbor 3; then dequeue 2, neighbor 3 already visited.

3. Step 3: Visit remaining node 3

   Dequeue 3, no new neighbors.

4. Final Answer:

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

5. Quick Check:

   BFS order = [0, 1, 2, 3] [OK]

Hint: BFS visits neighbors in queue order [OK]

Common Mistakes:

• Visiting nodes in DFS order instead
• Mixing neighbor order causing wrong sequence
• Not marking visited nodes causing repeats

4. The following BFS code snippet has a bug. What is the error?

void bfs(int start, int n, int adj[][n]) {
  int visited[n];
  for(int i=0; i<n; i++) visited[i] = 0;
  int queue[n], front=0, rear=0;
  queue[rear++] = start;
  visited[start] = 1;
  while(front < rear) {
    int u = queue[front++];
    printf("%d ", u);
    for(int v=0; v<n; v++) {
      if(adj[u][v] == 1 && visited[v] == 0) {
        queue[rear++] = v;
        // Missing visited mark here
      }
    }
  }
}

medium

A. Visited array is not initialized

B. Queue overflow not checked

C. Visited mark missing inside neighbor loop

D. Start node not enqueued

Solution

1. Step 1: Check visited array initialization

   Visited array is initialized to 0 for all nodes, so no issue here.

2. Step 2: Inspect neighbor loop for visited marking

   Inside the neighbor loop, nodes are enqueued but visited[v] is not set to 1, causing repeated visits.

3. Step 3: Confirm other options

   Queue overflow is not handled but not the main bug; start node is enqueued correctly.

4. Final Answer:

   Visited mark missing inside neighbor loop -> Option C

5. Quick Check:

   Mark visited when enqueueing neighbors [OK]

Hint: Always mark visited when enqueueing nodes [OK]

Common Mistakes:

• Forgetting to mark visited inside neighbor loop
• Assuming initialization fixes all visited issues
• Ignoring queue overflow but it's not main bug

5. Given a graph with nodes 0 to 4 and edges: 0-1, 0-2, 1-3, 2-3, 3-4. Using BFS starting at node 0, which node is visited at the 3rd step (0-based index)?

hard

A. 2

B. 3

C. 1

D. 4

Solution

1. Step 1: List BFS order from node 0

   Start at 0, enqueue neighbors 1 and 2. Visit order so far: [0]

2. Step 2: Visit nodes in queue order

   Visit 1 (step 1), enqueue neighbor 3; visit 2 (step 2), neighbor 3 already enqueued.

3. Step 3: Visit node 2 (step 3)

   Next node dequeued is 2, which is the 3rd step (0-based index).

4. Final Answer:

   2 -> Option A

5. Quick Check:

   BFS step 3 node = 2 [OK]

Hint: Track BFS queue order stepwise [OK]

Common Mistakes:

• Counting steps starting at 1 instead of 0
• Visiting neighbors out of enqueue order
• Forgetting node 3 is enqueued twice but visited once