Augment depth-first search with a two-valued colour:Each tree edge receives opposite endpoint colours. If an inspected edge has equal colours, the preceding parity argument produces an odd cycle, so the graph is not bipartite. If the procedure succeeds, every edge has differently coloured endpoints, and the two colour classes are a bipartition. The outer loop handles disconnected graphs and isolated vertices.
paint(v, c):
colour[v] = c
for w in adjacency[v]:
if colour[w] is unset:
if not paint(w, 1-c):
return false
else if colour[w] == c:
return false
return true
for v in V:
if colour[v] is unset:
if not paint(v, 0):
return false
return trueEach vertex is coloured once and each edge incidence is checked once, giving time and extra space with adjacency lists. No separate cycle enumeration is required.
Articles by others on the same topic
There are currently no matching articles.