Given an undirected (potentially disconnected) Graph G = (V, E), is G bipartite? In O(|V| + |E|)

Question

Telling whether a given connected graph is bipartite/2-colorable in O(|V| + |E|) is relatively simple with a BFS approach. This however will not work with disconnected graphs since other subgraphs may not be reachable from the vertex supplied to BFS. I can't think of any approach that doesn't involve looping over all vertices and running BFS for each node, which would blow the runtime up by another factor of |V|. Is there any way around this?

Answer 1

As you perform BFS, you already need to label the vertices as explored. This lets you do essentially what you described - loop over all vertices and run BFS for each one - but skip the redundant ones.

Specifically, loop over all vertices of the graph. When you get to a vertex $v$, if it hasn't been explored by a previous breadth-first search, do another breadth-first search starting from $v$ to determine if $v$'s component is bipartite.

You will only search each component once, so this is still $O(|V|+|E|)$.