c - How to implement the shortcutting step in the Christofides algorithm?

Question

I am implementing the Christofides algorithm for getting a 3/2-approximation to TSP in graphs that obey the triangle inequality. I already have code for computing a minimum spanning tree using Kruskal's algorithm and an adjacency matrix.

Now, I want to implement Christofides by doubling the edges and finding an Euler tour and then shortcutting duplicate nodes. How do I perform this step? I'd like the algorithm and (optionally) C code.

Thanks!

Answer 1

“捷径”步骤通过从 Euler 环中删除所有已在环中至少出现一次的节点来工作。例如，如果您参加了巡回演出

A → B → A → D → A → E → A

你会以循环结束

A → B → D → E → A

一种方法如下。维护一组到目前为止您在游览中访问过的所有节点。当您沿着游览走时，如果您遇到未访问的节点，请将其附加到您的循环中并将其添加到集合中。如果遇到访问过的节点，请跳过它。最后，将找到的最后一个节点的边添加回起始节点。

希望这可以帮助！