Minimum Spanning Tree -- Prim's Algorithm
Step-by-Step Animation
Animation Speed
Elaboration:
?
2）然后选取与VT中的点相连的未被选取过且使得边权最小的点，加入VT
3）然后重复步骤2直到所有点都被选取
Minimum Spanning Tree: Find a set of edges that connect every node in the original graph with minimum total cost(weight)
Prim's Algorithm: It builds the minimum spanning tree node by node by using a multimap or priority queue data structure.(Our animation uses multimap)
Algorithm Details:
(1) Start by inserting an arbitrary starting node's adjacent edges onto the multimap keyed on its edge weight.
(2) Remove the first element from the multimap and add its edge to the minimum spanning tree. Then we process the destination node by adding its adjacent edges onto the multimap, if the edge's destination node is not in the spanning tree and improves the destination node's current distance.
(3) Repeat step (2) until the multimap is empty.
最小生成树-prim算法定义：最小生成树就是用最少的代价来使得一个图连通。
Steps：
1）先在图中任意选一个起点，将其放入一个集合VT中 2）然后选取与VT中的点相连的未被选取过且使得边权最小的点，加入VT
3）然后重复步骤2直到所有点都被选取