com.mhhe.clrs2e
Class ConnectedComponents

java.lang.Object
  |
  +--com.mhhe.clrs2e.ConnectedComponents

public class ConnectedComponents

extends java.lang.Object

Runs the connected components algorithm on page 500 of Introduction to Algorithms, Second edition.

Field Summary

private java.lang.Object[]	handle An array of handles mapping vertices to sets.
private com.mhhe.clrs2e.DisjointSetUnion	sets A disjoint-set union structure for components.

Constructor Summary

ConnectedComponents(com.mhhe.clrs2e.Graph g)
Creates disjoint sets for the connected components of a graph.

Method Summary

boolean

sameComponent(com.mhhe.clrs2e.Vertex u, com.mhhe.clrs2e.Vertex v) Returns a boolean value indicating whether two vertices are in the same connected component.

Methods inherited from class java.lang.Object

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

Field Detail

sets

private com.mhhe.clrs2e.DisjointSetUnion sets

A disjoint-set union structure for components.

handle

private java.lang.Object[] handle

An array of handles mapping vertices to sets. The vertex whose index is i has a reference to the set of its connected component in handle[i].

Constructor Detail

ConnectedComponents

public ConnectedComponents(com.mhhe.clrs2e.Graph g)

Creates disjoint sets for the connected components of a graph. When done, handle[i] references the disjoint set corresponding to the connected component containing the vertex whose index is i.

Parameters:

g - The graph.

Method Detail

sameComponent

public boolean sameComponent(com.mhhe.clrs2e.Vertex u,
                             com.mhhe.clrs2e.Vertex v)

Returns a boolean value indicating whether two vertices are in the same connected component.

Parameters:

u - One vertex.

v - The other vertex.

Returns:

true if u and v are in the same connected component, false otherwise.