Check Bipartite Graph in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
int g[5][5] = {{0,1,0,1,0},{1,0,1,0,0},{0,1,0,1,0},{1,0,1,0,1},{0,0,0,1,0}}, color[5];
int dfs(int u, int c) {
    color[u] = c;
    for (int v = 0; v < 5; v++)
        if (g[u][v]) {
            if (!color[v] && !dfs(v, 3 - c)) return 0;
            if (color[v] == c) return 0;
        }
    return 1;
}
int main() {
    printf("Is Bipartite: %s", dfs(0,1) ? "Yes" : "No");
}

C Output

Input:
Edges = (0–1), (1–2), (2–3), (3–0), (3–4)
Output:
Input: 5-node undirected graph

Output:
Is Bipartite: Yes

C++ Program

#include <iostream>
#include <vector>
using namespace std;
bool dfs(int u, vector<vector<int>>& g, vector<int>& color, int c) {
    color[u] = c;
    for (int v : g[u])
        if (!color[v] && !dfs(v, g, color, 3 - c)) return false;
        else if (color[v] == c) return false;
    return true;
}
int main() {
    vector<vector<int>> g = {{1,3}, {0,2}, {1,3}, {0,2}};
    vector<int> color(4);
    cout << "Is Bipartite: " << (dfs(0, g, color, 1) ? "Yes" : "No");
}

C++ Output

Input:
Edges = (0–1), (1–2), (2–3), (3–0)
Output:
Input: 4-node cycle

Output:
Is Bipartite: Yes

JAVA Program

import java.util.*;
class Main {
    static boolean dfs(int u, List<List<Integer>> g, int[] color, int c) {
        color[u] = c;
        for (int v : g.get(u)) {
            if (color[v] == 0 && !dfs(v, g, color, 3 - c)) return false;
            if (color[v] == c) return false;
        }
        return true;
    }
    public static void main(String[] args) {
        int n = 5;
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        int[][] edges = {{0,1},{1,2},{2,3},{3,0},{3,4}};
        for (int[] e : edges) { g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); }
        int[] color = new int[n];
        System.out.println("Is Bipartite: " + (dfs(0, g, color, 1) ? "Yes" : "No"));
    }
}

JAVA Output

Input:
Graph edges: (0–1), (1–2), (2–3), (3–0), (3–4)
Output:
Input: 5-node undirected graph

Output:
Is Bipartite: Yes

Python Program

g = {0:[1,3], 1:[0,2], 2:[1,3], 3:[0,2], 4:[]}
color = {}
def dfs(u, c):
    color[u] = c
    for v in g[u]:
        if v not in color:
            if not dfs(v, 3 - c): return False
        elif color[v] == c: return False
    return True
print("Is Bipartite:", "Yes" if dfs(0,1) else "No")

Python Output

Input:
Graph: 0–1–2–3–0 (Cycle of 4), node 4 isolated
Output:
Input: Undirected graph dictionary

Output:
Is Bipartite: Yes

In-Depth Explanation

Example

Consider the Python graph:

0–1–2–3–0 is a 4-node cycle.

It is bipartite because you can divide the graph into two groups:

{0,2} and {1,3} so that no adjacent nodes are in the same group.

Node 4 is isolated, which is trivially bipartite.

Real-Life Analogy

Imagine seating guests at a dinner where some pairs don't get along and need to sit opposite each other across the table.

Can you seat the enemies so that no two of them are on the same side?

That's precisely what bipartite checking guarantees — a neat, two-sided separation.

Why It Matters

Bipartite checking aids in:

Graph coloring

Team division problems

Scheduling conflicts

Matching algorithms (e.g., job assignment)

It's also a fundamental component of algorithms such as maximum matching in bipartite graphs.

Learning Insights

You'll discover:

How to apply DFS with alternate coloring

How recursion assists in conflict detection

Using graph traversal for classification

How bipartiteness uncovers symmetry or contradiction

Also familiarizes you with coloring problems, a central graph theory concept.

Interview & Real-World Use

Often asked in:

Graph theory questions

Verifying if graph is 2-colorable

Pre-step prior to bipartite matching

Applied in:

Resource assignment problems

Load balancing systems

Conflict-free team or task partition

Verifying if a graph is bipartite is a basic graph theory problem that consolidates your knowledge of node coloring, conflict identification, and symmetry in structures. It's convenient in systems where clashes have to be prevented — e.g., scheduling, team building, or matchmaking services. The DFS-based coloring method employed here is a simple and effective one, with code kept tidy and minimal in all four languages (C, C++, Java, and Python). With examples and observations shown, you'll be well-prepared to comprehend, use, and explain bipartite graph checks in interviews and practical scenarios.