Applications of the graph theory: search for paths in a network and analysis of their connectivity

Abstract

This article presents three algorhitms for the search of oriented paths in a digraph, based on the generation of a tree in which an exhaustive search is performed —breadth— first in the first one and depth-first in the second and third ones. The first one allows us to find the optimum paths between two vertices, the second permits the solution of the same problem and also finds the Hamiltonian paths beginning in one vertex or the cycles of any length, while the third one allows us to find all the paths or the Eulerian circuits. The article also describes two algorhitms that use the same type of techniques for the analysis of the connectivity of a graph. The first one permits the division of a non-connective graph into its connective parts while the second one permits the detection of bridges in connective graphs.