public class Bipartite extends Object
Bipartiteclass represents a data type for determining whether an undirected graph is bipartite or whether it has an odd-length cycle. The isBipartite operation determines whether the graph is bipartite. If so, the color operation determines a bipartition; if not, the oddCycle operation determines a cycle with an odd number of edges.
This implementation uses depth-first search.
The constructor takes time proportional to V + E
(in the worst case),
where V is the number of vertices and E is the number of edges.
Afterwards, the isBipartite and color operations
take constant time; the oddCycle operation takes time proportional
to the length of the cycle.
BipartiteX for a nonrecursive version that uses breadth-first
For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
|Constructor and Description|
Determines whether an undirected graph is bipartite and finds either a bipartition or an odd-length cycle.
|Modifier and Type||Method and Description|
Returns the side of the bipartite that vertex
Returns true if the graph is bipartite.
Unit tests the
Returns an odd-length cycle if the graph is not bipartite, and
public Bipartite(Graph G)
G- the graph
public boolean isBipartite()
trueif the graph is bipartite;
public boolean color(int v)
v- the vertex
vis on; two vertices are in the same side of the bipartition if and only if they have the same color
0 <= v < V
UnsupportedOperationException- if this method is called when the graph is not bipartite
public static void main(String args)
args- the command-line arguments