Bipartite Graph from Scratch (2026)
A bipartite graph is one whose vertices can be divided into two disjoint sets such that every edge connects vertices from different sets. Equivalently, it contains no odd-length cycles.
Bipartite graphs model matching problems, including job assignments, dating platforms, and network flows. Checking bipartiteness is done via two-coloring with BFS or DFS.
BFS-Based Bipartite Check
Two-coloring assigns colors 0 and 1 to vertices alternately. Starting from an uncolored vertex, BFS assigns the opposite color to each neighbor. A conflict (same-colored adjacent vertices) indicates non-bipartiteness.
The algorithm runs in O(V+E) and handles disconnected graphs by restarting from each uncolored vertex.
bool isBipartiteBFS(vector>& graph) {
int V = graph.size();
vector color(V, -1);
for (int start = 0; start < V; start++) {
if (color[start] != -1) continue;
queue q;
q.push(start); color[start] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : graph[u]) {
if (color[v] == -1) {
color[v] = 1 - color[u];
q.push(v);
} else if (color[v] == color[u]) return false;
}
}
}
return true;
} DFS-Based Bipartite Check
The DFS-based approach follows the same two-coloring logic recursively. It is more memory-efficient for deep graphs and easily integrates with other graph processing logic.
DFS coloring also supports counting components and can be extended to find the two partitions explicitly.
bool dfsColor(int u, int c, vector>& graph, vector& color) {
color[u] = c;
for (int v : graph[u]) {
if (color[v] == -1) {
if (!dfsColor(v, 1 - c, graph, color)) return false;
} else if (color[v] == color[u]) return false;
}
return true;
}
bool isBipartiteDFS(vector>& graph) {
int V = graph.size();
vector color(V, -1);
for (int i = 0; i < V; i++)
if (color[i] == -1 && !dfsColor(i, 0, graph, color)) return false;
return true;
} Frequently Asked Questions
What is two-coloring in bipartite graphs?
Two-coloring assigns one of two colors to each vertex so that adjacent vertices always have different colors. A graph is bipartite exactly when it admits a valid two-coloring.
Can a bipartite graph have cycles?
Yes, but only even-length cycles. Odd-length cycles make two-coloring impossible because the cycle would require conflicting colors at closure.
Originally published on Ayodhyyya. Last updated June 1, 2026.