Question: What will the spanning tree look like after Prim's algorithm adds the first four edges in the following graph, if it begins at the asterisked node? What is the final minimum spanning tree for the graph?
10 18 12 1
o-----o-----*-----o-----o
| | | | _/
12| 2| 1| 2| _/13
| 16 | 16 | 14 |/
o-----o-----o-----o
| | | |
1| 16| 5| 20|
| | | |
o-----o-----o-----o
15 2 22
Answer: After four edge additions we have
12
o o *-----o o
|
1|
|
o o o o
|
5|
|
o o-----o o
2
At the algorithm's termination we have
10 12 1
o-----o *-----o-----o
| | | |
12| 2| 1| 2|
| | | |
o o o o
| | |
1| 5| 20|
| | |
o-----o-----o o
15 2