public class CC extends java.lang.Object
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 id, count, areConnected, and size operations take constant time.
For additional documentation, see Section 4.1 of Algorithms, 4th Edition, by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
CC(Graph G)
Computes the connected components of the undirected graph G.
|
Modifier and Type | Method and Description |
---|---|
boolean |
areConnected(int v,
int w)
Are vertices v and w in the same connected component?
|
int |
count()
Returns the number of connected components.
|
int |
id(int v)
Returns the component id of the connected component containing vertex v.
|
static void |
main(java.lang.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
- the graphpublic int id(int v)
v
- the vertexpublic int size(int v)
v
- the vertexpublic int count()
public boolean areConnected(int v, int w)
v
- one vertexw
- the other vertexpublic static void main(java.lang.String[] args)