public class BipartiteX extends Object
BipartiteXclass represents a data type for determining whether an undirected graph is bipartite or whether it has an odd-length cycle. A graph is bipartite if and only if it has no 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 breadth-first search and is nonrecursive.
The constructor takes Θ(V + E) time in
in the worst case, where V is the number of vertices
and E is the number of edges.
Each instance method takes Θ(1) time.
It uses Θ(V) extra space (not including the graph).
Bipartite for a recursive version that uses depth-first search.
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 BipartiteX(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