Package edu.princeton.cs.algs4

Class 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 vertex is an integer between 0 and k–1, where k is the number of connected components. 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 Description
      CC​(EdgeWeightedGraph graph)
      Computes the connected components of the edge-weighted graph graph.
      CC​(Graph graph)
      Computes the connected components of the undirected graph graph.

    • Constructor Detail

      • CC

        public CC​(Graph graph)
        Computes the connected components of the undirected graph graph.
        Parameters:
        graph - the undirected graph

      • CC

        public CC​(EdgeWeightedGraph graph)
        Computes the connected components of the edge-weighted graph graph.
        Parameters:
        graph - 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

      • main

        public static void main​(String[] args)
        Unit tests the CC data type.
        Parameters:
        args - the command-line arguments