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:
“Gwine to run all night!
Gwine to run all day!
I’ll bet my money on de bobtail nag—
Somebody bet on de bay.”
—Stephen Collins Foster (1826–1864)
“Too bad that all the people who know how to run the country are busy driving taxicabs and cutting hair.”
—George Burns (b. 1896)