在有向图中寻找哈密顿回路的快速回溯法

Quick Backward Search Algorithm for Finding All Hamilton Circuits in Directed Graph

本文提出了回路段的新概念。并在此基础上给出了寻找有向图中所有哈密顿回路 的快速回溯法ＱＢ．算法ＱＢ通过合并回路段来生成哈密顿回路，它的回溯树上各顶 点的期望分枝数ｃｑ等于各层当前图可用顶点的最小出度的平均值。对于常规的简单 回溯法ＳＢ，回溯树上各顶点的期望分枝数ｃｓ等于各层当前可用顶点的平均出度的 平均值。显然，ｃｑ总是小于ｃｓ．算法ＱＢ的期望时间为Ｏ（ｎ２（ｃｑ）ｎ），而算法ＳＢ期 望时间为Ｏ（ｎ（ｃｓ）ｎ），ｎ为图中顶点数。

In this article, a new concept-the segmental circuit is given. Based on the new concept, a Quick Backward Search Algorithm (Algorithm QB) is given. It spans Hamilton circuits by unioning segmental circuits. For Algorithm QB, cq, the expected branch number of the vertices on its Backward Search Tree, is equal to the average of the minimum outdegree of the useful vertices on the present graph of each level. For regular simple Backward Search Alg-orithm (Algorithm SB), Cs, the expected branch number of the vertices on its Backward Search Tree, is equal to the average of the average outdegree of the useful vertices on the present graph of each level. Obviously, cq is less than cs. The expected running time of Algorithm QB is O(n2(cq)n), the expected running time of Algorithm SB is O(n (cs)n), where n is the number of vertices on the graph.