Pseudo Code
Approx-TSP-Tour(G = (V, E), c)
1. select a vertex r Î V[G] to be a "root" vertex
2. compute a minimum spanning tree T for G from root r using MST-Prim(G, c, r)
3. let L be the list of vertices visited in a preorder tree walk of T
4. return the hamiltonian cycle H that visits the vertices in the order L
END
MST-PRIM (G = (V,E), c, r )
1. for each vertex
u ÎV[G]
2.
do key[u]
:=
¥
3.
p[u]
:=
NIL
/*p[u]
ia parent of node u */
4. key[r] := 0
5.
Q := V[G]
/*Q is a priority queue of set of all vertices not
in the tree */
6. while Q
¹ {}
7. do
u:= EXTRACT-MIN(Q)
8.
for each v Î Adj[u]
9.
do if v Î Q and c(u,v) < key[v]
10.
then p[v] := u
11.
key[v] := c(u,v)
END
If you can not open this applet with Internet Explorer, use Netscape 6 or higher, or use Mozilla.