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:

    One has to have run a household before one can know the price of rice and firewood, and one has to have raised children before one can understand a parent’s love.
    Chinese proverb.

    A real man doesn’t have to run from his mother, and may even have to face the reality that no great deed is going to be great enough for him to ransom himself completely, and he may always be in his mother’s debt. If he understands that . . . he won’t have to feel guilty, and he won’t have to please her completely. He can go ahead and be nice to her and let her be part of his life.
    Frank Pittman (20th century)