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:
“Sleep, beloved, such a sleep
As did that wild Tristram know
When, the potion’s work being done,
Roe could run or doe could leap
Under oak and beechen bough,
Roe could leap or doe could run....”
—William Butler Yeats (1865–1939)
“Lancaster bore him such a little town,
Such a great man. It doesn’t see him often
Of late years, though he keeps the old homestead
And sends the children down there with their mother
To run wild in the summer a little wild.”
—Robert Frost (1874–1963)