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:
“These are God’s own horses, poor, timid creatures, that will run fast enough as soon as they smell you, though they are nine feet high.”
—Henry David Thoreau (1817–1862)
“While waiting to get married, several forms of employment were acceptable. Teaching kindergarten was for those girls who stayed in school four years. The rest were secretaries, typists, file clerks, or receptionists in insurance firms or banks, preferably those owned or run by the family, but respectable enough if the boss was an upstanding Christian member of the community.”
—Barbara Howar (b. 1934)