[Java] Graph bipartition (2 coloring)

Given a graph, return a possible 2 coloring of it.

The algorithm is simple, for each node in the graph, if it doesn't yet have a color, run a DFS from it.

The DFS will assign a default color (eg; 1) to the node, if it doesn't already have one, then for each neighbor:

• if it already has a color which is NOT different from the current node color, break and fail
• if it doesn't have a color, assign the OPPOSITE of the current node color (eg use formula 1 - node color to invert between 0 and 1), then run a DFS from that node

In the end, if we stopped early it means the graph can't be colored with only 2 colors (there is no possible bipartition), otherwise we will have a possible 2 coloring or our graph as output.

This algorithm runs in O(V) space and O(E) time as for each node we explore all its neighbors once (we don't invoke DFS again unless neighbor had no color) and at most we can put V nodes on the callstack for recursion.

You can check my implementation of twoColor on my Gist along with some tests in TwoColorBipartitionJTests.