Find Strongly Connected Components in a Directed Graph

From NovaOrdis Knowledge Base
Revision as of 22:07, 4 October 2021 by Ovidiu (talk | contribs) (→‎Algorithm)
Jump to navigation Jump to search

External

Internal

Overview

Finding strongly connected components in a directed graph is a form of clustering heuristics: strongly connected components represent clusters where the objects represented by the vertices are clustered in some way.

Strongly connected components of a directed graph can be computed with Kosaraju's Two-Pass algorithm, which consists of two passes of depth-first search.

Kosaraju's Two-Pass Algorithm