public class CC extends Object
CC
class represents a data type for
determining the connected components in an undirected graph.
The id operation determines in which connected component
a given vertex lies; the connected operation
determines whether two vertices are in the same connected component;
the count operation determines the number of connected
components; and the size operation determines the number
of vertices in the connect component containing a given vertex.
The component identifier of a connected component is one of the
vertices in the connected component: two vertices have the same component
identifier if and only if they are in the same connected component.
This implementation uses depth-first search. The constructor takes Θ(V + E) time, 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).
For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
CC(EdgeWeightedGraph G)
Computes the connected components of the edge-weighted graph
G . |
CC(Graph G)
Computes the connected components of the undirected graph
G . |
Modifier and Type | Method and Description |
---|---|
boolean |
areConnected(int v,
int w)
Deprecated.
Replaced by
connected(int, int) . |
boolean |
connected(int v,
int w)
Returns true if vertices
v and w are in the same
connected component. |
int |
count()
Returns the number of connected components in the graph
G . |
int |
id(int v)
Returns the component id of the connected component containing vertex
v . |
static void |
main(String[] args)
Unit tests the
CC data type. |
int |
size(int v)
Returns the number of vertices in the connected component containing vertex
v . |
public CC(Graph G)
G
.G
- the undirected graphpublic CC(EdgeWeightedGraph G)
G
.G
- the edge-weighted graphpublic int id(int v)
v
.v
- the vertexv
IllegalArgumentException
- unless 0 <= v < V
public int size(int v)
v
.v
- the vertexv
IllegalArgumentException
- unless 0 <= v < V
public int count()
G
.G
public boolean connected(int v, int w)
v
and w
are in the same
connected component.v
- one vertexw
- the other vertextrue
if vertices v
and w
are in the same
connected component; false
otherwiseIllegalArgumentException
- unless 0 <= v < V
IllegalArgumentException
- unless 0 <= w < V
@Deprecated public boolean areConnected(int v, int w)
connected(int, int)
.v
and w
are in the same
connected component.v
- one vertexw
- the other vertextrue
if vertices v
and w
are in the same
connected component; false
otherwiseIllegalArgumentException
- unless 0 <= v < V
IllegalArgumentException
- unless 0 <= w < V
public static void main(String[] args)
CC
data type.args
- the command-line arguments