A New Algorithm for Finding all Tours and Hamiltonian Circuits in Graphs

摘要

This paper presents a new algorithm that finds all tours and Hamiltonian circuits in graphs. The algorithm makes the search for tours through the construction of n (number of nodes do graph) trees, one for each node of the graph. In the tree, all possible paths are configured from the initial node to the other nodes without repetition. The n-1 long paths are the tours of the graph. When a tour is in the tree and there is an edge in the graph connecting the end node to the start node of this tour, then a Hamiltonian circuit was found. The algorithm is easy to program and does not use recursion. The algorithm was applied to solve a problem of operational research within the graph theory. Several computational experiments were produced to measure the performance of the method in consolidated problem instances of literature.