Package edu.princeton.cs.algs4
Class Bipartite
 Object

 edu.princeton.cs.algs4.Bipartite

public class Bipartite extends Object
TheBipartite
class represents a data type for determining whether an undirected graph is bipartite or whether it has an oddlength cycle. A graph is bipartite if and only if it has no oddlength 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 depthfirst search. The constructor takes Θ(V + E) time 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
BipartiteX
for a nonrecursive version that uses breadthfirst search.For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 Author:
 Robert Sedgewick, Kevin Wayne


Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
color(int v)
Returns the side of the bipartite that vertexv
is on.boolean
isBipartite()
Returns true if the graph is bipartite.static void
main(String[] args)
Unit tests theBipartite
data type.Iterable<Integer>
oddCycle()
Returns an oddlength cycle if the graph is not bipartite, andnull
otherwise.



Constructor Detail

Bipartite
public Bipartite(Graph G)
Determines whether an undirected graph is bipartite and finds either a bipartition or an oddlength 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 vertexv
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
 unless0 <= v < V
UnsupportedOperationException
 if this method is called when the graph is not bipartite

oddCycle
public Iterable<Integer> oddCycle()
Returns an oddlength cycle if the graph is not bipartite, andnull
otherwise. Returns:
 an oddlength cycle if the graph is not bipartite
(and hence has an oddlength cycle), and
null
otherwise

main
public static void main(String[] args)
Unit tests theBipartite
data type. Parameters:
args
 the commandline arguments

