Minimum Spanning Tree（最小生成树，MST）

《CLRS》讨论MST的前提是Connected Undirected but Weighted Graph。MST是一棵连接所有vertices的树，具备树中所有Edge权重和最小的特性。（注意与Shortest Path的区别，不一样的）

理解Cut-Set

Cut-Set是一个Edge的集成，它将所有的Vertex分成了至少两个parts。在Kruskal算法中，Cut-Set不是很明显，比如在算法最开始，parts的数量与vertex的数量一致。而在Prim算法中，始终能看到一个vertex不断增长的part。

Kruskal

Forest视角，每次选出一条Edge，满足Weight最小的同时不会形成Cycle。当所有Vertices都被连接时，就形成了MST。

sort all edges by cost in ascending order in E
T is initialized as an empty set
For each edge as e in E:
    if T+{e} has no cycle:
        T = T+{e}
T is MST

Kruskal算法的一个关键，在于如何高效的判断加入e之后T是否存在cycle。此时要用到disjoint set数据结构（或称为union find），edge的两个vertice如果不属于同一个union，就可以放心加入，一定没有cycle。union在这里就成了connected components。如果假设find操作的复杂度为\(O(\log{V})\)，union的复杂度为\(O(1)\)，判断cycle的耗时与find相同，因此Kruskal的时间复杂度为\(O(E\log{V})\)。

Prim

Tree视角，算法从任意一个vertex开始，每次选出一条Edge，满足cost最小的同时，连接新的vertex，让这棵树生长，最后得到的就是MST。

Prim(G,v):  # v is start vertex
    S = {v}
    T = an empty set
    create a minheap as EH    # Edge minHeap
    add all edges of v to EH  # edges in cut-set(S,V-S)
    while |S| != |V|: 
        extract the minimum cost edge as e and (a,b) in EH
        T = T + {e}
        S = S + {b}  # a is already in S
        maintain EH  # add all edges of b to EH,
                     # delete all edges (x,b) where x in S,
                     # that's the edges in cut-set(S,V-S)
    T is MST

Prim算法与Dijstra算法很相似，但又有根本的区别。Prim算法中的Heap，只有edge的cost，Prim关注MST。Dijstra算法中的Heap，保存shortest path cost from source vertex，Dijstra关注SP。

所有edges都从heap中过了一遍，再加上extract操作，Prim算法的复杂度为\(O((E+V)\log{E})\)。