Class TarjanSCC


  • public class TarjanSCC
    extends Object
    The TarjanSCC class represents a data type for determining the strong components in a digraph. The id operation determines in which strong component a given vertex lies; the areStronglyConnected operation determines whether two vertices are in the same strong component; and the count operation determines the number of strong components.

    The component identifier of a component is one of the vertices in the strong component: two vertices have the same component identifier if and only if they are in the same strong component.

    This implementation uses Tarjan's algorithm. 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 digraph). For alternative implementations of the same API, see KosarajuSharirSCC and GabowSCC.

    For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    Author:
    Robert Sedgewick, Kevin Wayne
    • Constructor Detail

      • TarjanSCC

        public TarjanSCC​(Digraph G)
        Computes the strong components of the digraph G.
        Parameters:
        G - the digraph
    • Method Detail

      • count

        public int count()
        Returns the number of strong components.
        Returns:
        the number of strong components
      • stronglyConnected

        public boolean stronglyConnected​(int v,
                                         int w)
        Are vertices v and w in the same strong component?
        Parameters:
        v - one vertex
        w - the other vertex
        Returns:
        true if vertices v and w are in the same strong component, and false otherwise
        Throws:
        IllegalArgumentException - unless 0 <= v < V
        IllegalArgumentException - unless 0 <= w < V
      • id

        public int id​(int v)
        Returns the component id of the strong component containing vertex v.
        Parameters:
        v - the vertex
        Returns:
        the component id of the strong component containing vertex v
        Throws:
        IllegalArgumentException - unless 0 <= v < V
      • main

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