Connected Components Using BFS in DSA C - Build from Scratch

Connected Components Using BFS

📖 Scenario: You are working with a simple network of computers represented as an undirected graph. Each computer is a node, and connections between them are edges. You want to find how many separate groups of connected computers exist in the network.

🎯 Goal: Build a program that uses Breadth-First Search (BFS) to find and count the number of connected components in an undirected graph.

📋 What You'll Learn

Create an adjacency matrix to represent the graph with 6 nodes.

Create a visited array to track visited nodes.

Implement BFS to traverse connected nodes.

Count and print the number of connected components.

💡 Why This Matters

🌍 Real World

Finding connected components helps identify isolated groups in networks like social media, computer networks, or road maps.

💼 Career

Understanding graph traversal and connected components is essential for roles in software development, data analysis, and network engineering.

1

Create the Graph Adjacency Matrix

Create a 6x6 integer adjacency matrix called graph with these exact connections (undirected): edges between nodes 0-1, 0-2, 1-2, 3-4. Use 1 for connected and 0 for no connection. Initialize all other entries to 0.

DSA C

# Your code here

Hint

Use a 2D array with 6 rows and 6 columns. Put 1 where nodes are connected and 0 otherwise.

2

Create the Visited Array

Create an integer array called visited of size 6 and initialize all elements to 0 to track if a node has been visited.

DSA C

int graph[6][6] = {
    {0, 1, 1, 0, 0, 0},
    {1, 0, 1, 0, 0, 0},
    {1, 1, 0, 0, 0, 0},
    {0, 0, 0, 0, 1, 0},
    {0, 0, 0, 1, 0, 0},
    {0, 0, 0, 0, 0, 0}
};

# Your code here

Hint

Use an integer array with 6 zeros to mark all nodes as not visited.

3

Implement BFS Function

Write a function called bfs that takes an integer start, the graph adjacency matrix, and the visited array. Use a queue to visit all nodes connected to start. Mark nodes as visited when they are dequeued.

DSA C

int graph[6][6] = {
    {0, 1, 1, 0, 0, 0},
    {1, 0, 1, 0, 0, 0},
    {1, 1, 0, 0, 0, 0},
    {0, 0, 0, 0, 1, 0},
    {0, 0, 0, 1, 0, 0},
    {0, 0, 0, 0, 0, 0}
};

int visited[6] = {0, 0, 0, 0, 0, 0};

// Your code here

Hint

Use an array as a queue with front and rear indices. Mark nodes visited when added to the queue.

4

Count and Print Connected Components

Write a main function that uses bfs to count how many connected components are in the graph. For each node from 0 to 5, if it is not visited, call bfs on it and increment a counter. Then print the count with printf("%d\n", count);.

DSA C

#include 
#include 

int graph[6][6] = {
    {0, 1, 1, 0, 0, 0},
    {1, 0, 1, 0, 0, 0},
    {1, 1, 0, 0, 0, 0},
    {0, 0, 0, 0, 1, 0},
    {0, 0, 0, 1, 0, 0},
    {0, 0, 0, 0, 0, 0}
};

int visited[6] = {0, 0, 0, 0, 0, 0};

void bfs(int start) {
    int queue[6];
    int front = 0, rear = 0;
    queue[rear++] = start;
    visited[start] = 1;

    while (front < rear) {
        int current = queue[front++];
        for (int i = 0; i < 6; i++) {
            if (graph[current][i] == 1 && visited[i] == 0) {
                queue[rear++] = i;
                visited[i] = 1;
            }
        }
    }
}

// Your code here

Hint

Loop through all nodes, call bfs if not visited, and count how many times bfs is called. Print the count.