Prim's Algorithm - Example Run

Example Run

Image U possible edges V \ U Description
{} {A,B,C,D,E,F,G} This is our original weighted graph. The numbers near the edges indicate their weight.
{D} {D,A} = 5 V
{D,B} = 9
{D,E} = 15
{D,F} = 6
{A,B,C,E,F,G} Vertex D has been arbitrarily chosen as a starting point. Vertices A, B, E and F are connected to D through a single edge. A is the vertex nearest to D and will be chosen as the second vertex along with the edge AD.
{A,D} {D,B} = 9
{D,E} = 15
{D,F} = 6 V
{A,B} = 7
{B,C,E,F,G} The next vertex chosen is the vertex nearest to either D or A. B is 9 away from D and 7 away from A, E is 15, and F is 6. F is the smallest distance away, so we highlight the vertex F and the edge DF.
{A,D,F} {D,B} = 9
{D,E} = 15
{A,B} = 7 V
{F,E} = 8
{F,G} = 11
{B,C,E,G} The algorithm carries on as above. Vertex B, which is 7 away from A, is highlighted.
{A,B,D,F} {B,C} = 8
{B,E} = 7 V
{D,B} = 9 cycle
{D,E} = 15
{F,E} = 8
{F,G} = 11
{C,E,G} In this case, we can choose between C, E, and G. C is 8 away from B, E is 7 away from B, and G is 11 away from F. E is nearest, so we highlight the vertex E and the edge BE.
{A,B,D,E,F} {B,C} = 8
{D,B} = 9 cycle
{D,E} = 15 cycle
{E,C} = 5 V
{E,G} = 9
{F,E} = 8 cycle
{F,G} = 11
{C,G} Here, the only vertices available are C and G. C is 5 away from E, and G is 9 away from E. C is chosen, so it is highlighted along with the edge EC.
{A,B,C,D,E,F} {B,C} = 8 cycle
{D,B} = 9 cycle
{D,E} = 15 cycle
{E,G} = 9 V
{F,E} = 8 cycle
{F,G} = 11
{G} Vertex G is the only remaining vertex. It is 11 away from F, and 9 away from E. E is nearer, so we highlight G and the edge EG.
{A,B,C,D,E,F,G} {B,C} = 8 cycle
{D,B} = 9 cycle
{D,E} = 15 cycle
{F,E} = 8 cycle
{F,G} = 11 cycle
{} Now all the vertices have been selected and the minimum spanning tree is shown in green. In this case, it has weight 39.

Read more about this topic:  Prim's Algorithm

Famous quotes containing the word run:

    When a thought of Plato becomes a thought to me,—when a truth that fired the soul of Pindar fires mine, time is no more. When I feel that we two meet in a perception, that our two souls are tinged with the same hue, and do as it were run into one, why should I measure degrees of latitude, why should I count Egyptian years?
    Ralph Waldo Emerson (1803–1882)

    Adrenalin dispels boredom. Run, you sufferers from ennui! Run for your lives!
    Mason Cooley (b. 1927)