Click or drag to resize
TarjanSCC Class

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 time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the Id, Count, and AreStronglyConnected operations take constant time. For alternate implementations of the same API, see and .

Inheritance Hierarchy
SystemObject
  Algs4NetTarjanSCC

Namespace: Algs4Net
Assembly: Algs4Net (in Algs4Net.dll) Version: 1.0.0.0 (1.0.0.0)
Syntax
C#
Copy
public class TarjanSCC

The TarjanSCC type exposes the following members.

Constructors
  NameDescription
Public methodTarjanSCC
Computes the strong components of the digraph G.
Top
Properties
  NameDescription
Public propertyCount
Returns the number of strong components.
Top
Methods
  NameDescription
Public methodId
Returns the component id of the strong component containing vertex v.
Public methodStatic memberMainTest
Demo test the TarjanSCC data type.
Public methodStronglyConnected
Are vertices v and w in the same strong component?
Top
Remarks

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

This class is a C# port from the original Java class TarjanSCC implementation by the respective authors.

See Also