哈密顿环
1、问题描述
设G =(V,E)是一个n 结点的连通图。一个哈密顿环是一条沿着图G 的n 条边环行的路径, 它访问每个结点一次并且返回到它的开始位置。
图G1含有一个哈密顿环1->2 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 1
2、找下一个结点的算法
过程NEXTVALUE给出了在求哈密顿环的过程中如何找下一个结点的算法。
|
procedure NEXTVALUE( k)
∥X(1) , ⋯ , X( k - 1) 是一条有k - 1 个不同结点的路径。若X( k ) = 0 , 则表示再无结点可分配给X(k) 。若还有与X(1) , ⋯ ,X( k - 1) 不同且与X( k - 1) 有边相连接的结点, 则将其中标数最高的结点置于X(k) 。若k = n , 则还需与X(1) 相连接∥
global integer n , X( 1∶n) , boolean GRAPH (1∶n , 1∶n)
integer k , j
loop
X( k )← (X(k) + 1) mod ( n + 1) ∥下一个结点∥
if X( k) = 0 then return endif
if GRAPH (X( k - 1 ) , X( k) ) ∥有边相连吗∥
then for j←1 to k - 1 do ∥检查与前k - 1 个结点是否相同∥
if X( j ) = X( k)
then exit ∥有相同结点, 出此循环∥
endif
repeat
if j = k ∥若为真, 则是一个不同结点∥
then if k < n or ( k = n and GRAPH(X( n ) , 1 ) ) then return
endif
endif
endif
repeat
end NEXTVALUE
|
3、找所有的哈密顿环
|
procedure H AMILTONIAN( k )
∥这是找出图G中所有哈密顿环的递归算法。图G用它的布尔邻接矩阵GRAP H(1∶n ,1
∶n)表示。每个环都从结点1开始
global integer X(1∶n)
local integer k , n
loop ∥生成X( k) 的值∥
call NEXTVALUE(k ) ∥下一个合法结点分配给X( k) ∥
if X( k) = 0 then return endif
if k = n
then print (X,‘1’) ∥打印一个环∥
else call H AMILTONIAN( k + 1)
endif
repeat
end HAMILTONIAN
|
这个过程首先初始化邻接矩阵GRAPH(1∶n ,1∶n), 然后置X(2∶n) ←0 ,X( 1) ←1 ,再执行callHAMILTONIAN( 2)。