Pattern Guide
Bipartite Graphs & Matching
"2-colorable = bipartite. BFS/DFS detects it. Matching pairs them up optimally."
A bipartite graph divides vertices into two groups with edges only between groups (no edges within a group). Check with 2-coloring (BFS/DFS). Maximum bipartite matching finds the most pairs. Many scheduling, assignment, and conflict-detection problems reduce to bipartite checking or matching.
16 min readgraph problems →
Problems you can solve with this pattern
4 problems · click any to start solving
Check if graph is bipartite using BFS 2-coloring
function isBipartite(graph) {
const n = graph.length;
const color = new Array(n).fill(-1); // -1=uncolored, 0=left, 1=right
for (let start = 0; start < n; start++) {
if (color[start] !== -1) continue; // already colored
color[start] = 0;
const queue = [start];
while (queue.length) {
const u = queue.shift();
for (const v of graph[u]) {
if (color[v] === -1) {
color[v] = 1 - color[u]; // opposite color
queue.push(v);
} else if (color[v] === color[u]) {
return false; // same color = odd cycle = not bipartite
}
}
}
}
return true;
}
// DFS version:
function isBipartiteDFS(graph) {
const color = new Array(graph.length).fill(-1);
const dfs = (u, c) => {
color[u] = c;
for (const v of graph[u]) {
if (color[v] === c) return false;
if (color[v] === -1 && !dfs(v, 1-c)) return false;
}
return true;
};
for (let i = 0; i < graph.length; i++)
if (color[i] === -1 && !dfs(i, 0)) return false;
return true;
}A graph is bipartite if its vertices can be split into two groups such that every edge goes between the groups (no edge within a group). Equivalently: the graph has no odd-length cycle. Equivalently: it's 2-colorable (can be 2-colored with no two adjacent vertices sharing a color). Check in O(V+E) with BFS/DFS.
Bipartite Check — 2-Coloring
Check if graph is bipartite using BFS 2-coloring
function isBipartite(graph) {
const n = graph.length;
const color = new Array(n).fill(-1); // -1=uncolored, 0=left, 1=right
for (let start = 0; start < n; start++) {
if (color[start] !== -1) continue; // already colored
color[start] = 0;
const queue = [start];
while (queue.length) {
const u = queue.shift();
for (const v of graph[u]) {
if (color[v] === -1) {
color[v] = 1 - color[u]; // opposite color
queue.push(v);
} else if (color[v] === color[u]) {
return false; // same color = odd cycle = not bipartite
}
}
}
}
return true;
}
// DFS version:
function isBipartiteDFS(graph) {
const color = new Array(graph.length).fill(-1);
const dfs = (u, c) => {
color[u] = c;
for (const v of graph[u]) {
if (color[v] === c) return false;
if (color[v] === -1 && !dfs(v, 1-c)) return false;
}
return true;
};
for (let i = 0; i < graph.length; i++)
if (color[i] === -1 && !dfs(i, 0)) return false;
return true;
}Maximum Bipartite Matching (Hungarian / Augmenting Path)
Maximum bipartite matching: Find the maximum set of edges where no vertex appears twice.
Augmenting path algorithm (O(V×E)):
1. For each left vertex, try to match it to an unmatched right vertex
2. If right vertex is already matched, try to re-match its current left partner to another right vertex (augmenting path)
3. If successful, increase matching count
König's theorem: min vertex cover = max matching in bipartite graph.
Augmenting path algorithm (O(V×E)):
1. For each left vertex, try to match it to an unmatched right vertex
2. If right vertex is already matched, try to re-match its current left partner to another right vertex (augmenting path)
3. If successful, increase matching count
König's theorem: min vertex cover = max matching in bipartite graph.
Hungarian algorithm for maximum bipartite matching
function maxBipartiteMatching(graph, leftSize, rightSize) {
const matchL = new Array(leftSize).fill(-1); // matchL[i] = right node matched to left i
const matchR = new Array(rightSize).fill(-1); // matchR[j] = left node matched to right j
function dfs(u, visited) {
for (const v of graph[u]) {
if (visited[v]) continue;
visited[v] = true;
if (matchR[v] === -1 || dfs(matchR[v], visited)) {
matchL[u] = v;
matchR[v] = u;
return true;
}
}
return false;
}
let matching = 0;
for (let u = 0; u < leftSize; u++) {
const visited = new Array(rightSize).fill(false);
if (dfs(u, visited)) matching++;
}
return { matching, matchL, matchR };
}Bipartite problem signals:
- "Can we divide into two groups with no conflict within a group?" → bipartite check
- "Two-color problem / enemy-of-enemy-is-friend" → bipartite check
- "Max pairs / assignments between two sets" → bipartite matching
- "Min vertex cover of bipartite graph" = max matching (König's theorem)
- "Max independent set of bipartite graph" = n - max matching
Bipartite check = no odd cycle:
- BFS 2-coloring: O(V+E), works for disconnected graphs
- Union-Find: doesn't directly detect odd cycles (need special handling)
- "Can we divide into two groups with no conflict within a group?" → bipartite check
- "Two-color problem / enemy-of-enemy-is-friend" → bipartite check
- "Max pairs / assignments between two sets" → bipartite matching
- "Min vertex cover of bipartite graph" = max matching (König's theorem)
- "Max independent set of bipartite graph" = n - max matching
Bipartite check = no odd cycle:
- BFS 2-coloring: O(V+E), works for disconnected graphs
- Union-Find: doesn't directly detect odd cycles (need special handling)