基本上,一旦您对节点的随机选择以一种方式构造了图,使得最后一个顶点A没有未访问的相邻顶点,则需要使一个顶点可用以继续。
为此,请执行以下操作:随机选择一个相邻的顶点,删除其现有的一条边(在哈密顿路径中,任何单个顶点只能有两条边),然后从当前顶点到当前可用的随机选择的一条点绘制一条新边。然后,您从随机选择的顶点跟踪到图形的末尾(第一个只有一个边的顶点),并继续执行算法。
在各种可怕的伪代码中:
Graph graph;
Vertex current;
Path path;
while(!IsHamiltonian(path))
{
if(HasUnvisitedNeighbor(current, path))
{
Vertex next = SelectRandomUnvisited(current, path);
DrawEdgeTo(next, current, path);
current= next;
}
else
{
Vertex next = SelectRandomNeighbor(current, path);
RemoveRandomEdgeFrom(next, path);
DrawEdgeTo(next, current, path);
path = FindEnd(next, current, path); //Finds the end of the path, starting from next, without passing through current
}
}