Click or drag to resize
Bipartite Class

The Bipartite 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 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.

See for a nonrecursive version that uses breadth-first search.

Inheritance Hierarchy
SystemObject
  Algs4NetBipartite

Namespace: Algs4Net
Assembly: Algs4Net (in Algs4Net.dll) Version: 1.0.0.0 (1.0.0.0)
Syntax
C#
Copy
public class Bipartite

The Bipartite type exposes the following members.

Constructors
  NameDescription
Public methodBipartite
Determines whether an undirected graph is bipartite and finds either a bipartition or an odd-length cycle.
Top
Properties
  NameDescription
Public propertyG
Returns the graph for which the bipartite is computed
Public propertyIsBipartite
Returns true if the graph is bipartite.
Top
Methods
  NameDescription
Public methodColor
Returns the side of the bipartite that vertex v is on.
Public methodStatic memberMainTest
Demo test the Bipartite data type.
Public methodOddCycle
Returns an odd-length cycle if the graph is not bipartite, and null otherwise.
Top
Remarks

For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

This class is a C# port from the original Java class Bipartite implementation by the respective authors.

See Also