Pattern visualizer
Bipartite Graph Check
Color nodes one component at a time with BFS: give the start node color 0, then force every uncolored neighbor to the OPPOSITE color and queue it. The only way this can fail is a neighbor that is already colored and happens to match — which can only happen if some cycle has odd length, because walking around an even cycle always alternates back to the opposite color of where you started, while an odd cycle forces two ends of the same edge to agree. Loop over every starting node so a disconnected graph gets checked component by component. Animated on: 7 nodes, two components: the 4-cycle 0-1-2-3-0 and the triangle 4-5-6-4 — can every node be colored with only two colors so no edge joins two same-colored nodes?.
BFS two-coloring: an edge between same-colored nodes proves it's impossible
Undirected graph, every node uncolored
7 nodes. A graph is bipartite only if every node can be painted one of two colors so that no edge joins two nodes of the SAME color — so color node by node and let an edge that disagrees prove it can't be done.
1FUNCTION isBipartite(n, edges):2 BUILD adjacency LIST FROM edges3 color <- ARRAY of n VALUES -14 FOR start FROM 0 TO n - 15 IF color[start] != -1: CONTINUE6 color[start] <- 0; queue <- [start]7 WHILE queue NOT EMPTY8 u <- REMOVE FIRST FROM queue9 FOR EACH v IN adjacency[u]10 IF color[v] = -111 color[v] <- 1 - color[u]; APPEND v TO queue12 ELSE IF color[v] = color[u]13 RETURN false14 RETURN true
← / → step · space play · Home restart