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:
“Knowledge has two extremes. The first is the pure natural ignorance in which all men find themselves at birth. The other extreme is that reached by great minds, who, having run through all that men can know, find they know nothing, and come back again to that same natural ignorance from which they set out; this is a learned ignorance which is conscious of itself.”
—Blaise Pascal (1623–1662)
“Power, I said. Power to walk into the gold vaults of the nations, into the secrets of kings, into the holy of holies. Power to make multitudes run squealing in terror at the touch of my little invisible finger. Even the moon’s frightened of me. Frightened to death. The whole world’s frightened to death.”
—R.C. Sherriff (1896–1975)