Class KosarajuSharirSCC

  • public class KosarajuSharirSCC
    extends Object
    The KosarajuSharirSCC 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 the Kosaraju-Sharir 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 TarjanSCC and GabowSCC.

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

    Robert Sedgewick, Kevin Wayne
    • Constructor Detail

      • KosarajuSharirSCC

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

      • count

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

        public boolean stronglyConnected​(int v,
                                         int w)
        Are vertices v and w in the same strong component?
        v - one vertex
        w - the other vertex
        true if vertices v and w are in the same strong component, and false otherwise
        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.
        v - the vertex
        the component id of the strong component containing vertex v
        IllegalArgumentException - unless 0 <= s < V
      • main

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