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.

Practice

1. What does it mean for a graph to be bipartite?

easy

A. It contains at least one cycle

B. Its vertices can be divided into two sets with no edges inside the same set

C. It has an equal number of vertices and edges

D. All vertices have the same degree

Solution

1. Step 1: Understand bipartite graph definition

   A bipartite graph is one where vertices can be split into two groups so that no edge connects vertices within the same group.

2. Step 2: Compare options with definition

   Only Its vertices can be divided into two sets with no edges inside the same set matches this definition exactly. Other options describe unrelated properties.

3. Final Answer:

   Its vertices can be divided into two sets with no edges inside the same set -> Option B

4. Quick Check:

   Bipartite graph = two sets, no same-set edges [OK]

Hint: Bipartite means two groups with no internal edges [OK]

Common Mistakes:

• Confusing bipartite with equal vertices and edges
• Thinking bipartite means no cycles
• Assuming all vertices have same degree

2. Which of the following C code snippets correctly initializes a graph adjacency list for bipartite check?

easy

A. int graph[5][5] = {{0}};

B. int graph[5]; for(int i=0; i<5; i++) graph[i] = NULL;

C. int graph[][] = {0};

D. int* graph[5]; for(int i=0; i<5; i++) graph[i] = malloc(sizeof(int)*5); memset(graph[i], 0, sizeof(int)*5);

Solution

1. Step 1: Understand adjacency list initialization in C

   Adjacency list uses array of pointers to arrays or linked lists. int* graph[5]; for(int i=0; i<5; i++) graph[i] = malloc(sizeof(int)*5); memset(graph[i], 0, sizeof(int)*5); correctly allocates memory and initializes it.

2. Step 2: Check other options for correctness

   int graph[5][5] = {{0}}; is a fixed 2D array but only zero-initialized; B tries to assign NULL to int array elements (invalid); C has incomplete array declaration.

3. Final Answer:

   int* graph[5]; for(int i=0; i<5; i++) graph[i] = malloc(sizeof(int)*5); memset(graph[i], 0, sizeof(int)*5); -> Option D

4. Quick Check:

   Proper adjacency list init = malloc + memset [OK]

Hint: Use malloc and memset to init adjacency lists in C [OK]

Common Mistakes:

• Trying to assign NULL to int array elements
• Using incomplete array declarations
• Not allocating memory for adjacency lists

3. Given the following graph edges: 0-1, 1-2, 2-3, 3-0, what will the bipartite check function return?

medium

A. Runtime error due to cycle

B. false (graph is not bipartite)

C. true (graph is bipartite)

D. Indeterminate result

Solution

1. Step 1: Analyze the graph structure

   The edges form a cycle of length 4: 0-1-2-3-0. Even length cycles can be bipartite, so this graph is bipartite.

2. Step 2: Check bipartite condition on cycle

   Since the cycle length is even, the graph can be colored with two colors without conflict.

3. Final Answer:

   true (graph is bipartite) -> Option C

4. Quick Check:

   Even cycle = bipartite [OK]

Hint: Even length cycles are bipartite, odd length are not [OK]

Common Mistakes:

• Assuming all cycles are not bipartite
• Confusing cycle length parity
• Thinking runtime error occurs due to cycles

4. Identify the bug in this bipartite check code snippet:

bool isBipartite(int graph[][3], int V) {
  int color[V];
  for(int i=0; i

medium

A. Function does not check disconnected components

B. Color array is not initialized to -1

C. Queue is not initialized properly

D. Incorrect color assignment logic

Solution

1. Step 1: Understand the code logic

   The code colors nodes starting from node 0 and uses BFS to assign colors to neighbors.

2. Step 2: Identify missing checks

   The code only starts BFS from node 0 and does not check other disconnected components, which may cause incorrect results if graph is disconnected.

3. Step 3: Verify other options

   Queue is properly initialized; color array is initialized to -1; color assignment logic is correct.

4. Final Answer:

   Function does not check disconnected components -> Option A

5. Quick Check:

   Check all components for bipartite [OK]

Hint: Always check all graph components in bipartite check [OK]

Common Mistakes:

• Ignoring disconnected graph parts
• Assuming single BFS covers entire graph
• Misunderstanding color assignment

5. You have a graph with 6 vertices and edges: 0-1, 0-3, 1-2, 2-3, 4-5. Which statement is true about its bipartite nature?

hard

A. The graph is bipartite because all components are bipartite

B. The graph is not bipartite because of the cycle 0-1-2-3-0

C. The graph is bipartite only if vertex 4 is connected to vertex 2

D. The graph is not bipartite because vertices 4 and 5 form an odd cycle

Solution

1. Step 1: Analyze graph components

   Vertices 0-1-2-3 form a cycle 0-1-2-3-0 of length 4 (even), which is bipartite. Vertices 4-5 form a separate edge, also bipartite.

2. Step 2: Check bipartite condition for entire graph

   Since all components are bipartite, the entire graph is bipartite.

3. Step 3: Evaluate other options

   The graph is not bipartite because of the cycle 0-1-2-3-0 is wrong because even cycles are bipartite. The graph is bipartite only if vertex 4 is connected to vertex 2 is irrelevant. The graph is not bipartite because vertices 4 and 5 form an odd cycle is wrong because 4-5 is just an edge, no cycle.

4. Final Answer:

   The graph is bipartite because all components are bipartite -> Option A

5. Quick Check:

   All components bipartite = graph bipartite [OK]

Hint: Check each component's bipartite status separately [OK]

Common Mistakes:

• Assuming any cycle means not bipartite
• Ignoring disconnected components
• Confusing edges with cycles