BFS Breadth First Search on Graph in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS traversal on a simple graph

What is the output of the BFS traversal starting from node 0 in the given graph?

DSA C

/* Graph adjacency list representation:
   0: 1, 2
   1: 0, 3
   2: 0, 4
   3: 1
   4: 2
*/

void bfs(int start, int graph[][5], int n) {
    int queue[10], front = 0, rear = 0;
    int visited[5] = {0};
    queue[rear++] = start;
    visited[start] = 1;

    while (front < rear) {
        int node = queue[front++];
        printf("%d ", node);
        for (int i = 0; i < n; i++) {
            if (graph[node][i] == 1 && !visited[i]) {
                queue[rear++] = i;
                visited[i] = 1;
            }
        }
    }
}

int main() {
    int graph[5][5] = {
        {0,1,1,0,0},
        {1,0,0,1,0},
        {1,0,0,0,1},
        {0,1,0,0,0},
        {0,0,1,0,0}
    };
    bfs(0, graph, 5);
    return 0;
}

A [0, 2, 1, 4, 3]

B [0, 1, 2, 3, 4]

C [0, 1, 3, 2, 4]

D [0, 2, 4, 1, 3]

💡 Hint

Remember BFS visits neighbors level by level starting from the start node.

BFS starts at node 0, visits neighbors 1 and 2, then visits neighbors of 1 (which is 3) and neighbors of 2 (which is 4). So the order is 0, 1, 2, 3, 4.

🧠 Conceptual

intermediate

Number of nodes visited in BFS

Given a graph with 6 nodes where node 5 is disconnected, how many nodes will BFS visit starting from node 0?

A 6

B 1

C 4

D 5

💡 Hint

BFS only visits nodes reachable from the start node.

Since node 5 is disconnected, BFS starting at node 0 visits only the 5 connected nodes.

🔧 Debug

advanced

Identify the error in BFS implementation

What error will this BFS code produce when run on a graph with 4 nodes?

DSA C

void bfs(int start, int graph[][4], int n) {
    int queue[10], front = 0, rear = 0;
    int visited[4] = {0};
    queue[rear++] = start;
    visited[start] = 1;

    while (front < rear) {
        int node = queue[front++];
        printf("%d ", node);
        for (int i = 0; i < n; i++) {
            if (graph[node][i] == 1 && !visited[i]) {
                queue[rear++] = i;
                visited[i] = 1;
            }
        }
    }
}

A Runs correctly and prints BFS order

B Runtime error due to accessing queue out of bounds

C Compilation error due to wrong array size

D Infinite loop because front never exceeds rear

💡 Hint

Check the loop condition carefully.

The original loop condition 'front <= rear' causes the loop to run one extra time after the queue is empty, leading to reading invalid data and infinite loop. Changing it to 'front < rear' fixes the issue.

🚀 Application

advanced

Shortest path length using BFS

Using BFS on an unweighted graph, what is the shortest path length from node 0 to node 4?

DSA C

/* Graph adjacency list:
0: 1, 2
1: 3
2: 4
3: 4
4: 
*/

int bfs_shortest_path(int start, int end, int graph[][5], int n) {
    int queue[10], front = 0, rear = 0;
    int visited[5] = {0};
    int distance[5] = {0};
    queue[rear++] = start;
    visited[start] = 1;
    distance[start] = 0;

    while (front < rear) {
        int node = queue[front++];
        if (node == end) return distance[node];
        for (int i = 0; i < n; i++) {
            if (graph[node][i] == 1 && !visited[i]) {
                queue[rear++] = i;
                visited[i] = 1;
                distance[i] = distance[node] + 1;
            }
        }
    }
    return -1;
}

int main() {
    int graph[5][5] = {
        {0,1,1,0,0},
        {0,0,0,1,0},
        {0,0,0,0,1},
        {0,0,0,0,1},
        {0,0,0,0,0}
    };
    int dist = bfs_shortest_path(0, 4, graph, 5);
    printf("%d", dist);
    return 0;
}

A 1

B 3

C 2

D 4

💡 Hint

BFS finds shortest path in unweighted graphs by levels.

Shortest path from 0 to 4 is 0->2->4 or 0->1->3->4 but 0->2->4 is shorter with length 2.

❓ Predict Output

expert

BFS traversal order on a directed graph with cycles

What is the BFS traversal order starting from node 0 on the directed graph below?

DSA C

/* Directed graph adjacency matrix:
0 -> 1, 2
1 -> 2, 3
2 -> 0, 3
3 -> 3
*/

void bfs(int start, int graph[][4], int n) {
    int queue[10], front = 0, rear = 0;
    int visited[4] = {0};
    queue[rear++] = start;
    visited[start] = 1;

    while (front < rear) {
        int node = queue[front++];
        printf("%d ", node);
        for (int i = 0; i < n; i++) {
            if (graph[node][i] == 1 && !visited[i]) {
                queue[rear++] = i;
                visited[i] = 1;
            }
        }
    }
}

int main() {
    int graph[4][4] = {
        {0,1,1,0},
        {0,0,1,1},
        {1,0,0,1},
        {0,0,0,1}
    };
    bfs(0, graph, 4);
    return 0;
}

A [0, 1, 2, 3]

B [0, 2, 1, 3]

C [0, 1, 3, 2]

D [0, 2, 3, 1]

💡 Hint

BFS visits nodes in order of discovery and marks visited to avoid cycles.

Starting at 0, neighbors 1 and 2 are visited. Then from 1, neighbor 3 is visited. Node 2's neighbors are already visited. Node 3 points to itself but is already visited. So order is 0,1,2,3.