Question 2.100

70. Let G be a graph with weights assigned to each edge. Consider the following algorithm:

  1. Pick any vertex V of G.
  2. Select an edge E with a vertex at V that has a minimum weight. Let the other endpoints of E be W.
  3. Contract the edge VW so that edge VW disappears and vertices V and W coincide (see the following figures).
image

If in the new graph two or more edges join a pair of vertices, delete all but the cheapest. Continue to call the new vertex V.

(d) Repeat steps (b) and (c) until a single point is obtained. The edges selected in the course of this algorithm (called Prim’s algorithm) form a minimum-cost spanning tree. Apply this algorithm to the accompanying graphs.

image