Bipartite Graph Check in DSA C

Mental Model

A bipartite graph can be split into two groups where no nodes inside the same group connect to each other.

Analogy: Imagine two teams playing a game where players only pass the ball to the other team, never to their own teammates.

Group A: 1 -> 3 -> 5
Group B: 2 -> 4 -> 6
Edges only go between groups, never inside one group.

Dry Run Walkthrough

Input: Graph with edges: 1-2, 2-3, 3-4, 4-1 (square shape)

Goal: Check if the graph can be colored using two colors so that no connected nodes share the same color.

Step 1: Start coloring node 1 with color 0

Node colors: [1:0, 2:null, 3:null, 4:null]

Why: We pick a starting node and assign the first color.

Step 2: Color neighbors of node 1 with color 1 (node 2 and node 4)

Node colors: [1:0, 2:1, 3:null, 4:1]

Why: Neighbors must have opposite color to avoid same-group edges.

Step 3: Color neighbor of node 2 with color 0 (node 3)

Node colors: [1:0, 2:1, 3:0, 4:1]

Why: Continue alternating colors for connected nodes.

Step 4: Check neighbors of node 3: node 4 already colored 1, no conflict

Node colors: [1:0, 2:1, 3:0, 4:1]

Why: No two connected nodes share the same color, so far so good.

Step 5: All nodes colored without conflict, graph is bipartite

Node colors: [1:0, 2:1, 3:0, 4:1]

Why: Successful two-coloring means bipartite.

Result:

Node colors: [1:0, 2:1, 3:0, 4:1] -> Graph is bipartite

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX 101

// Graph represented as adjacency list
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* graph[MAX];
int color[MAX];
int n; // number of vertices

Node* createNode(int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

void addEdge(int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph[src];
    graph[src] = newNode;

    newNode = createNode(src);
    newNode->next = graph[dest];
    graph[dest] = newNode;
}

bool bfsCheck(int start) {
    int queue[MAX];
    int front = 0, rear = 0;
    queue[rear++] = start;
    color[start] = 0; // assign first color

    while (front < rear) {
        int u = queue[front++];
        Node* temp = graph[u];
        while (temp != NULL) {
            int v = temp->vertex;
            if (color[v] == -1) {
                color[v] = 1 - color[u]; // assign opposite color
                queue[rear++] = v;
            } else if (color[v] == color[u]) {
                return false; // same color on both ends means not bipartite
            }
            temp = temp->next;
        }
    }
    return true;
}

bool isBipartite() {
    for (int i = 1; i <= n; i++) {
        color[i] = -1; // initialize all colors to -1 (uncolored)
    }
    for (int i = 1; i <= n; i++) {
        if (color[i] == -1) {
            if (!bfsCheck(i)) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    n = 4;
    for (int i = 0; i <= n; i++) {
        graph[i] = NULL;
    }
    addEdge(1, 2);
    addEdge(2, 3);
    addEdge(3, 4);
    addEdge(4, 1);

    if (isBipartite()) {
        printf("Graph is bipartite\n");
    } else {
        printf("Graph is NOT bipartite\n");
    }
    return 0;
}

color[start] = 0; // assign first color

assign starting node color 0 to begin coloring

if (color[v] == -1) { color[v] = 1 - color[u]; queue[rear++] = v; }

assign opposite color to uncolored neighbor and enqueue it

else if (color[v] == color[u]) { return false; }

detect conflict if neighbor has same color, graph not bipartite

for (int i = 1; i <= n; i++) { if (color[i] == -1) { if (!bfsCheck(i)) return false; } }

check all components by running BFS coloring on unvisited nodes

Output

Graph is bipartite

Complexity Analysis

Time: O(V + E) because we visit every vertex and edge once during BFS

Space: O(V + E) for storing adjacency list and color array

vs Alternative: Compared to checking all pairs of nodes (O(V^2)), BFS coloring is much faster for sparse graphs

Edge Cases

Empty graph (no vertices)

Returns true since no edges exist to violate bipartite property

DSA C

for (int i = 1; i <= n; i++) { if (color[i] == -1) { if (!bfsCheck(i)) return false; } }

Graph with one vertex and no edges

Returns true because single node can be colored any color

DSA C

color[start] = 0; // assign first color

Graph with odd cycle (e.g., triangle 1-2-3-1)

Returns false because odd cycle cannot be bipartite

DSA C

else if (color[v] == color[u]) { return false; }

When to Use This Pattern

When you need to split nodes into two groups with no internal edges, use bipartite check with BFS or DFS coloring to detect conflicts.

Common Mistakes

Mistake: Not initializing all node colors to -1 before starting BFS
Fix: Initialize color array to -1 for all nodes before BFS to mark uncolored nodes

Mistake: Not checking all disconnected components in the graph
Fix: Run BFS coloring from every uncolored node to cover all components

Mistake: Assigning the same color to neighbors instead of opposite color
Fix: Assign neighbor color as 1 - current node color to ensure alternating colors

Summary

Checks if a graph can be divided into two groups with no edges inside the same group.

Use when you want to know if a graph is two-colorable or can be split into two sets without internal connections.

The key insight is to color nodes alternately and detect if any edge connects nodes of the same color.