Algorithm for constructing strongly connected components in digraphs
Nikola Ivačić · PeFprints (University of Ljubljana) · 2012
This thesis gives a detailed description of an algorithm for finding strongly connected components in a directed graph. The reader requires no prior knowledge of graph theory or algorithm analisys. We start by introducing graph theory as a problem space and a framework for a given algorithm. We define some fundamental constructs such as: what is a digraph, what are strongly connected components, and what are their basic properties. \tA description of a theoretical model of computation comes next. It serves as a founda- tion for the study of algorithm complexity and its correctness in general. We learn what is an algorithm, what is its complexity and correctness. \tIn order to analyse the algorithm for constructing strongly connected components of a given digraf we need to get familiar with basic datastructures and mathematical tools for algorithm construction. In the core of the thesis we present the algorithm of Tarjan, of Kusaraju-Sharir and the algorithm of Cheriyan-Mehlhorn/Gabow, together with the analisys of their complexity and proof of their correctenes. We deal with how the graph is presented in our model of computation and with mathematical theorems that are used as building blocks for the construction and analisys of the three algorithms.