2018/02/15 by Vlad-Andrei Munteanu, Munteanu, Vlad-Andrei
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1802.05387
7 pages, 5 sequences of code
arxiv created 2018/02/15 · arxiv updated 2018/02/16
A directed graph G (V, E) is strongly connected if and only if, for a pair of vertices X and Y from V, there exists a path from X to Y and a path from Y to X. In Computer Science, the partition of a graph in strongly connected components is represented by the partition of all vertices from the graph, so that for any two vertices, X and Y, from the same partition, there exists a path from X to Y and a path from Y to X and for any two vertices, U and V, from different partition, the property is not met. The algorithm presented below is meant to find the partition of a given graph in strongly connected components in O (numberOfNodes + numberOfEdges * log* (numberOfNodes)), where log* function stands for iterated logarithm.