edu.princeton.cs.algorithms

Class CC

java.lang.Object

edu.princeton.cs.algorithms.CC

public class CC
extends Object

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

Author:

Robert Sedgewick, Kevin Wayne

Constructor Summary

Constructors

Constructor and Description
CC(Graph G) Computes the connected components of the undirected graph G.

Method Summary

Methods

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(String[] args) Unit tests the CC data type.
int	size(int v) Returns the number of vertices in the connected component containing vertex v.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

CC

public CC(Graph G)

Computes the connected components of the undirected graph G.

Parameters:

G - the graph

Method Detail

id

public int id(int v)

Returns the component id of the connected component containing vertex v.

Parameters:

v - the vertex

Returns:

the component id of the connected component containing vertex v

size

public int size(int v)

Returns the number of vertices in the connected component containing vertex v.

Parameters:

v - the vertex

Returns:

the number of vertices in the connected component containing vertex v

count

public int count()

Returns the number of connected components.

Returns:

the number of connected components

areConnected

public boolean areConnected(int v,
                   int w)

Are vertices v and w in the same connected component?

Parameters:

v - one vertex

w - the other vertex

Returns:

true if vertices v and w are in the same connected component, and false otherwise

main

public static void main(String[] args)

Unit tests the CC data type.