Minimum Spanning Trees
General Solution：
GENERIC-MST(G, w)
1 A ← Ø
2 while A does not form a spanning tree
3 do find an edge (u, v) that is safe for A
4 A ← A ∪ {(u, v)}
5 return A
Kruskal's algorithm：
MST-KRUSKAL(G, w)
1 A ← Ø
2 for each vertex v ∈ V[G]
3 do MAKE-SET(v)
4 sort the edges of E into nondecreasing order by weight w
5 for each edge (u, v) ∈ E, taken in nondecreasing order by weight
6 do if FIND-SET(u) ≠ FIND-SET(v)
7 then A ← A ∪ {(u, v)}
8 UNION(u, v) //将两棵树中的root点进行合并
9 return A
Prim's algorithm：
MST-PRIM(G, w, r)
1 for each u ∈ V [G]
2 do key[u] ← ∞
3 π[u] ← NIL
4 key
← 0
5 Q ← V [G]
6 while Q ≠ Ø
7 do u ← EXTRACT-MIN(Q) //从Q中取出key值最小的点，加入到A中
8 for each v ∈ Adj[u]
9 do if v ∈ Q and w(u, v) < key[v]
10 then π[v] ← u
11 key[v] ← w(u, v)
//MST生成后，树中的点是通过π关系联结起来的，因此不用显示的“加入”到A中
