edu.princeton.cs.algs4

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. 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 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. 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 and Description
`BipartiteX(Graph G)`
Determines whether an undirected graph is bipartite and finds either a bipartition or an odd-length cycle.
• Method Summary

Methods
Modifier and Type Method and 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 Object

`clone, equals, finalize, 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