SECTION 2.2 Elementary Graph Theory 123
As with the Nearest-Neighbor algorithm, we do not select any edges
which would prematurely result in a cycle. Also, we need to avoid any
edges which will result in more than two edges from a given vertex.
Example.We consider this algorithm on the Midwestern Cities graph.
- Choose the{Chicago, Merriville}link as this is the cheapest among
all links. - Choose the{Merriville, Joliet}link; this is the second cheapest at
$120. - The third cheapest link is the {Gary, Merriville} link at $121;
however, choosing this link will result in three edges issuing from
Merriville. The fourth cheapest link is the{Chicago, Joliet}link
at $133. However, this is also impossible as a premature cycle is
formed. We settle for the{Gary, Highland}link at $150. - We choose the{Chicago, Highland}link at $152.
- The only remaining choice given the constraints is the {Gary,
Joliet}link at $200.
The above algorithm produces the Hamiltonian cycle
Chicago−→Merriville−→Joliet−→Gary−→Highland−→Chicago,
at a total (non-optimal) cost of $741.
The algorithm above are what are calledgreedy algorithmsas at
each stage they seek the optimal (i.e., cheapest) choice.
Exercises
- Apply the Cheapest-Link algorithm to the graph indicated in the
table in Exercise 1 on page 121. - Apply the Cheapest-Link algorithm to the graph indicated in the
table in Exercise 2 on page 122.