8.4.1 A Greedy Algorithm for TSP

• Based on Kruskal's algorithm. It only gives a suboptimal solution in general.
• Works for complete graphs. May not work for a graph that is not complete.
• As in Kruskal's algorithm, first sort the edges in the increasing order of weights.
• Starting with the least cost edge, look at the edges one by one and select an edge only if the edge, together with already selected edges,

1.

does not cause a vertex to have degree three or more

2.

does not form a cycle, unless the number of selected edges equals the number of vertices in the graph.

Example:

Consider the six city problem shown in Figure 8.14. The sorted set of edges is

{$\Big($(d, e), 3$\Big)$,$\Big($(b, c), 5$\Big)$,$\Big($(a, b), 5$\Big)$,$\Big($(e, f ), 5$\Big)$,$\Big($(a, c), 7.08$\Big)$,$\Big($(d, f ),$\sqrt{58}$$\Big)$,

$\Big($(b, e),$\sqrt{22}$$\Big)$,$\Big($(b, d ),$\sqrt{137}$$\Big)$,$\Big($(c, d ), 14$\Big)$,...$\Big($(a, f ), 18$\Big)$

See Figures 8.15 and 8.16.

Figure 8.15: An intermediate stage in the construction of a TSP tour

Select (d, e)
Select (a, b)
Select (b, c)
Select (e, f)
Reject (a, c)	since it forms a cycle with (a, b) and (b, c)
Reject (d, f)	since it forms a cycle with (d, e) and (e, f)
Reject (b, e)	since that would make the degree of b equal to 3
Reject (b, d)	for an identical reason
Select (c, d)
.
.
.
Select (a, f)
$\Downarrow$   This yields a total cost = 50, which is about 4% from the optimal cost.

Figure 8.16: A TSP tour for the six-city problem