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:
“Any man that resists the present tides that run in the world, will find himself thrown upon a shore so high and barren that it will seem he has been separated from his human kind forever.”
—Woodrow Wilson (1856–1924)
“I turn my head to sky rains falling,
wash the wounds of numbness from my soul.
Turn my heart in tides of fierce renewal,
where love and rage run whole.
Come drink deep.”
—Carolyn McDade (20th century)