24. Minimum Spanning Trees 2

The second algorithm for the MST problem is Prim’s algorithm, which also adopts the greedy policy.
In this case, the edges in A always form a single subtree. In contrast, the edges in A in the Kruskal’s algorithm always form a forest.

Prim’s algorithm

1. We start with A= empty, and a vertex set U={r},where r is any vertex in V.
2. Add a light edge' 2 node from U to A,
3. This procedure continues until the edges in A form a minimum spanning tree.
   Main concept:An edge "a" of least weight with exactly one of its endpoints being in U.

数据结构：

1. one priority queue: initially store all the node with value infinite in the graph.
2. a list: initially empty but aim to store all the MST nodes one by one.

流程:

1. pop one node A from the priority queue, according to graph matrix, obtain the distance between A with its neighbors
2. refresh their value in priority queue(keep smallest), during every time of the refreshing, do heapify on priority queue.
3. add A into list.

Continue doing until the priority queue is empty.

Time Complexity: 对每一个邻居都会做 heapify，即 |E| log|V|，其他时间都是constant。所以时间复杂度维 |E| log|V|。