Algorithms for finding the strongly connected components of directed graphsLANG, INA (Avtor)
Dobravec, Tomaž (Mentor)
graphstrong connectivitystrongly connectedTarjan’s algorithmKosaraju’s algorithmGabowpath-basedBlellochFleischerparallelism.One of the most common problems in graph theory is the problem of finding strongly connected components (SCCs). Decomposing a directed graph into strongly connected components is a fundamental tool in graph theory with applications in compiler analysis, data mining, scientific computing, and other areas. In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex in that graph. The strongly connected components of an arbitrary directed graph form a partition into subgraphs. Those subgraphs are themselves strongly connected.
In this bachelor thesis, we will introduce the problem mentioned above in detail. We will try to understand its importance by looking at its applications. Then we will proceed exploring different approaches for finding strongly connected components of a directed graph. Finally, we will inspect their advantages and disadvantages by comparing them and draw a conclusion as to which algorithm performs best in a given situation.20212021-09-13 20:15:18Diplomsko delo/naloga130334sl