Algorithms for path searching and for graph connectivity analysis

✍ Scribed by A. Recuero

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 980 KB
• Volume: 23
• Category: Article
• ISSN: 0965-9978
• DOI: 10.1016/0965-9978(95)00025-m

✦ Synopsis

Three algorithms for the search of oriented paths in digraphs are described, based in the generation of a tree, in which an BFS is done, in the first one, and a DFS is done, in the other two algorithms. The first one is aimed at finding all the optimum paths between two vertices. The second one is aimed at solving this problem, as well as at finding the Hamiltonian paths beginning in a vertex, or at finding all the cycles of any order in the digraph. The third one is aimed at finding all the Eulerian paths or circuits. Two more algorithms, for the analysis of graph connectivity, using the same type of techniques are also described, one aimed at separating an unconnected graph into connected subgraphs, and the other aimed at searching for all existing bridges. All five algorithms are fully described and they are also implemented in a structured form, using QB as the programming language. A very compact scheme is proposed to store all the required information, using only one-dimension arrays without pointers, which allows simple programming languages to be used.