Towards an Automatic Derivation of Tarjan's Algorithm for Detecting Strongly Connected Components in Directed Graphs
Harmen L. A. van der Spek · 2006
Ideally, algorithms should be easy to understand and perform efficiently. However, these two requirements are often contradicting. In this thesis, by describing a semi-automatic derivation of an efficient algorithm for detecting strongly connected components, we argue that efficiency may be derivable, thereby satisfying both requirements. First, some basic graph theory will be reviewed. Then we will focus on some existing algorithms, among which Tarjan’s algorithm is the most well known. Some attention is given to parallel algorithms for detecting strongly connected components. Next, we start with a simple but inefficient algorithm for detecting strongly connected components. This algorithm will be transformed step-by-step into a more efficient algorithm. Finally, we will present some test results and compare the efficiency of the resulting algorithm to Tarjan’s algorithm.