基于邻接矩阵和递归算法的哈密顿回路研究

Research on Hamiltonian Loop Based on Adjacency Matrix and Recursive Algorithm

哈密顿链或路径本身就是简单链或路径是解决商旅问题的重要手段。尽管哈密顿链或路径等概念与相应的欧拉链和路径的概念相似,但是很难知道一个图或有向图是否存在这样的现象并且计算量较大。文章通过了解哈密顿图的定义,结合解图存在哈密顿回路的充分条件,使用C++编写代码以实现10个城市之间航线的哈密顿回路的路径的长度的计算以及比较,并得出最佳路线。结果表明,基于邻接矩阵和递归算法可以快速求解哈密顿回路问题,并用冒泡排序对路径大小做比较,从而得出最佳路线。

The Hamilton chain or path itself is a simple chain or path and is an important means to solve business travel problems.Although concepts such as Hamiltonian chains or paths are similar to the corresponding concepts of European zippers and paths,it is difficult to know whether such a phenomenon exists in a graph or a directed graph and the amount of calculation is relatively large.By understanding the definition of the Hamiltonian diagram,combining the sufficient conditions for the existence of the Hamiltonian loop in the solution graph,the article uses C++to write code to calculate and compare the path length of the Hamiltonian loop between 10cities,and find the best route.The results show that the Hamiltonian loop problem can be solved quickly based on the adjacency matrix and the recursive algorithm,and the bubble sorting is used to compare the path sizes to obtain the best route.