1. Two colors
0 uncolored, then 1 and -1 for the two sides.
const color = new Array(n).fill(0)Typorithm · medium
Bipartite Check
▷ Interactive algorithm labbipartite-checkgraph-algorithmstwo-coloringbfsconflict
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Bipartite Check
Graph Algorithms
BFS two-color the graph; a same-color edge between neighbors means it is not bipartite.
A graph is bipartite if its nodes split into two sets with every edge crossing between them.
BFS assigns each node the opposite color of its parent, spreading two colors outward.
If an edge ever connects two nodes of the same color, no valid split exists.
Preparing algorithm lab…
01
Neighbors get opposite colors.
02
Same-color edge = not bipartite.
03
Repeat for every component.
function isBipartite(graph, n) {
const color = new Array(n).fill(0);
for (let start = 0; start < n; start += 1) {
if (color[start] !== 0) continue;
color[start] = 1;
const queue = [start];
while (queue.length > 0) {
const node = queue.shift();
for (const next of graph[node]) {
if (color[next] === 0) {
color[next] = -color[node];
queue.push(next);
} else if (color[next] === color[node]) {
return false;
}
}
}
}
return true;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Each component
Restart coloring for every unvisited component.
if (color[start] !== 0) continue3. Opposite color
A neighbor must get the opposite color of the current node.
color[next] = -color[node]4. Conflict
Two adjacent nodes with the same color make the graph non-bipartite.
else if (color[next] === color[node])5. Not bipartite
A same-color edge proves no valid two-coloring exists.
return falseA complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.