Algorithms for finding the strongly connected components of directed graphs

Abstract
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.

Language: English graph, strong connectivity, strongly connected, Tarjan’s algorithm, Kosaraju’s algorithm, Gabow, path-based, Blelloch, Fleischer, parallelism. Bachelor thesis/paper (mb11) 2.11 - Undergraduate Thesis FRI - Faculty of computer and information science 2021 77685251 107 20 (0 votes) Voting is allowed only to logged in users. AddThis uses cookies that require your consent. Edit consent...

## Secondary language

Language: Slovenian Algoritmi za iskanje močno povezanih komponent usmerjenih grafov Eden od najpogostejših problemov v teoriji grafov je problem iskanja močno povezanih komponent usmerjenega grafa. Razgradnja samega usmerjenega grafa v močno povezane komponente predstavlja pomembno orodje v teoriji grafov, ki je uporabno pri analizi prevajalnikov, podatkovnem rudarjenju in na ostalih področjih. V matematični teoriji pravimo, da je graf močno povezan, če za vsaki dve njegovi vozlišči velja, da sta dosegljivi med seboj. Prav tako mora za vsako od močno povezanih komponent poljubnega usmerjenega grafa veljati, da tudi sama predstavlja močno povezan graf. V tem diplomskem delu bomo podrobno predstavili zgoraj omenjeni problem. Preko njegove aplikacije bomo poskušali razumeti njegov pomen. Nato bomo raziskali različne pristope za iskanje močno povezanih komponent usmerjenih grafov. Na koncu bomo s primerjavo preučili njihove prednosti in pomanjkljivosti ter iz tega sklepali, kateri algoritem je ustrezen v določeni situaciji. graf, močna povezanost, močno povezane komponente, Kosaraju, Tarjan, Gabow, Blelloch, Fleischer, vzporednost.