Bipartite Graph Check
An interactive, step-by-step visualisation of Bipartite Graph Check.
- Category
- Graphs
- Time complexity
- O(V + E)
- Space complexity
- O(V)
Pseudocode
color[start] = A BFS: neighbor gets the opposite color same-color neighbor found ⇒ not bipartite
Reference implementation
def is_bipartite(adj):
color = {}
for s in adj:
if s in color: continue
color[s] = 0; q = [s]
while q:
u = q.pop(0)
for v in adj[u]:
if v not in color: color[v] = 1-color[u]; q.append(v)
elif color[v] == color[u]: return False
return True