edu.princeton.cs.algs4

Class CC

Object

edu.princeton.cs.algs4.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 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.

Author:

Robert Sedgewick, Kevin Wayne

Constructor Summary

Constructors

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.

Method Summary

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.

Methods inherited from class 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 undirected graph

CC

public CC(EdgeWeightedGraph G)

Computes the connected components of the edge-weighted graph G.

Parameters:

G - the edge-weighted 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

Throws:

IllegalArgumentException - unless 0 <= v < 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

Throws:

IllegalArgumentException - unless 0 <= v < V

count

public int count()

Returns the number of connected components in the graph G.

Returns:

the number of connected components in the graph G

connected

public boolean connected(int v,
                         int w)

Returns true if vertices v and w are 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; false otherwise

Throws:

IllegalArgumentException - unless 0 <= v < V

IllegalArgumentException - unless 0 <= w < V

areConnected

@Deprecated
public boolean areConnected(int v,
                                        int w)

Deprecated. Replaced by connected(int, int).

Returns true if vertices v and w are 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; false otherwise

Throws:

IllegalArgumentException - unless 0 <= v < V

IllegalArgumentException - unless 0 <= w < V

main

public static void main(String[] args)

Unit tests the CC data type.

Parameters:

args - the command-line arguments