Bipartite Graph Check in DSA C - Build from Scratch

Bipartite Graph Check

📖 Scenario: You are working on a social network app where users can be grouped into two sets such that no two users within the same set are friends. This means the friendship graph is bipartite. You want to check if the friendship connections form a bipartite graph.

🎯 Goal: Build a program in C that checks if a given undirected graph is bipartite using a coloring method.

📋 What You'll Learn

Use an adjacency list to represent the graph

Use an array to store colors of nodes

Implement a BFS or DFS to assign colors and check bipartiteness

Print 1 if the graph is bipartite, else print 0

💡 Why This Matters

🌍 Real World

Bipartite graphs are used in matching problems like job assignments, social networks, and scheduling.

💼 Career

Understanding bipartite graphs is important for software engineers working on graph algorithms, network analysis, and optimization problems.

1

Create the graph adjacency list

Create an integer variable n and set it to 4. Create an adjacency list array graph of size 4, where each element is an integer array representing connected nodes. Initialize graph[0] with {1, 3}, graph[1] with {0, 2}, graph[2] with {1, 3}, and graph[3] with {0, 2}. Also create an integer array graph_sizes with values {2, 2, 2, 2} representing the number of neighbors for each node.

DSA C

# Your code here

Hint

Use a 2D array for the adjacency list and an array for sizes of each node's neighbors.

2

Create the color array and initialize it

Create an integer array color of size n and initialize all elements to -1 to represent uncolored nodes.

DSA C

int n = 4;
int graph[4][2] = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
int graph_sizes[4] = {2, 2, 2, 2};
// Your code here

Hint

Use -1 to mark nodes as uncolored initially.

3

Implement BFS to check bipartite

Write a function int bfs_check(int start) that uses a queue to assign colors 0 and 1 to nodes starting from start. Initialize color[start] to 0. While the queue is not empty, dequeue a node u and for each neighbor v in graph[u], if color[v] is -1, assign color[v] to 1 - color[u] and enqueue v. If color[v] equals color[u], return 0 (not bipartite). If BFS finishes without conflict, return 1.

DSA C

int n = 4;
int graph[4][2] = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
int graph_sizes[4] = {2, 2, 2, 2};
int color[4] = {-1, -1, -1, -1};

// Your code here

Hint

Use a simple array as a queue with front and rear indices. Assign colors alternately and check for conflicts.

4

Check all nodes and print result

In main(), iterate over all nodes from 0 to n-1. If color[i] is -1, call bfs_check(i). If any call returns 0, print 0 and return 0. If all calls return 1, print 1.

DSA C

int n = 4;
int graph[4][2] = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
int graph_sizes[4] = {2, 2, 2, 2};
int color[4] = {-1, -1, -1, -1};

int bfs_check(int start) {
    int queue[100];
    int front = 0, rear = 0;
    color[start] = 0;
    queue[rear++] = start;

    while (front < rear) {
        int u = queue[front++];
        for (int i = 0; i < graph_sizes[u]; i++) {
            int v = graph[u][i];
            if (color[v] == -1) {
                color[v] = 1 - color[u];
                queue[rear++] = v;
            } else if (color[v] == color[u]) {
                return 0;
            }
        }
    }
    return 1;
}

int main() {
    for (int i = 0; i < n; i++) {
        if (color[i] == -1) {
            // Your code here
        }
    }
    return 0;
}

Hint

Check each node if uncolored, run bfs_check. If any returns 0, print 0 and exit. Otherwise print 1.