BipartiteX Class |
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 for a recursive version that uses depth-first search.
Namespace: Algs4Net
public class BipartiteX
The BipartiteX type exposes the following members.
Name | Description | |
---|---|---|
BipartiteX | Determines whether an undirected graph is bipartite and finds either a
bipartition or an odd-length cycle. |
Name | Description | |
---|---|---|
G |
Returns the graph for which the bipartite is computed
| |
IsBipartite |
Returns true if the graph is bipartite. |
Name | Description | |
---|---|---|
Color |
Returns the side of the bipartite that vertex v is on. | |
MainTest |
Demo test the BipartiteX data type. | |
OddCycle |
Returns an odd-length cycle if the graph is not bipartite, and
null otherwise. |
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 BipartiteX implementation by the respective authors.