Class BipartiteX

• Object
• edu.princeton.cs.algs4.BipartiteX

• ```public class BipartiteX
extends Object```
The `BipartiteX` class 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). See `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.

Author:
Robert Sedgewick, Kevin Wayne
• Constructor Summary

Constructors
Constructor Description
`BipartiteX​(Graph G)`
Determines whether an undirected graph is bipartite and finds either a bipartition or an odd-length cycle.
• Method Summary

All Methods
Modifier and Type Method Description
`boolean` `color​(int v)`
Returns the side of the bipartite that vertex `v` is on.
`boolean` `isBipartite()`
Returns true if the graph is bipartite.
`static void` `main​(String[] args)`
Unit tests the `BipartiteX` data type.
`Iterable<Integer>` `oddCycle()`
Returns an odd-length cycle if the graph is not bipartite, and `null` otherwise.
• Methods inherited from class java.lang.Object

`clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• Constructor Detail

• BipartiteX

`public BipartiteX​(Graph G)`
Determines whether an undirected graph is bipartite and finds either a bipartition or an odd-length cycle.
Parameters:
`G` - the graph
• Method Detail

• isBipartite

`public boolean isBipartite()`
Returns true if the graph is bipartite.
Returns:
`true` if the graph is bipartite; `false` otherwise
• color

`public boolean color​(int v)`
Returns the side of the bipartite that vertex `v` is on.
Parameters:
`v` - the vertex
Returns:
the side of the bipartition that vertex `v` is on; two vertices are in the same side of the bipartition if and only if they have the same color
Throws:
`IllegalArgumentException` - unless `0 <= v < V`
`UnsupportedOperationException` - if this method is called when the graph is not bipartite
• oddCycle

`public Iterable<Integer> oddCycle()`
Returns an odd-length cycle if the graph is not bipartite, and `null` otherwise.
Returns:
an odd-length cycle if the graph is not bipartite (and hence has an odd-length cycle), and `null` otherwise
• main

`public static void main​(String[] args)`
Unit tests the `BipartiteX` data type.
Parameters:
`args` - the command-line arguments