Graph AlgosGraph Algorithms

Bipartite Check (BFS 2-coloring)

Colour vertices with two colours so every edge joins different colours; succeeds iff the graph has no odd cycle.

Learn Bipartite Check →
ABCDEFGHIJKL
Queue
empty
1/26A graph is bipartite iff it can be 2-colored so that every edge joins different colors. BFS forces the coloring: each neighbor must take the opposite color, so any conflict proves an odd cycle.
Color 0Color 1Current nodeEdge used to color a neighborConflict: both ends same color
PseudocodeLearn Bipartite Check →
1color = {}
2for s in nodes:
3  if s in color: continue
4  color[s] = 0; queue = [s]
5  while queue not empty:
6    u = queue.popleft()
7    for v in neighbors(u):
8      if v not in color: color[v] = 1 - color[u]; queue.append(v)
9      elif color[v] == color[u]: return NOT bipartite
10return bipartite
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V)
Speed