安全邊：在每一次迭代之前， A是某個(gè)最小生成樹(shù)的一個(gè)子集。在算法的每一步中，確定一條邊（u,v),使得將它加入集合A后，仍然不違反這個(gè)循環(huán)不等式，A U {(u,v)}仍然是某一個(gè)最小生成樹(shù)的子集。稱(chēng)這樣的邊為A的安全邊。
識(shí)別安全邊的定理：設(shè)圖G=(V,E)是一個(gè)無(wú)向連通圖，并且在E上定義了一個(gè)具有實(shí)數(shù)值的加權(quán)函數(shù)w.設(shè)A是E的一個(gè)子集，它包含于G的某個(gè)最小生成樹(shù)中。設(shè)割(S,V-S)是G的任意一個(gè)不妨害A的割，且邊(u,v)是通過(guò)割(S,V-S)的一條輕邊，則邊(u,v)對(duì)集合A來(lái)說(shuō)是安全的。
推論：設(shè)G=(V,E)是一個(gè)無(wú)向聯(lián)通圖，并且在E上定義了相應(yīng)的實(shí)數(shù)值加權(quán)函數(shù)w.設(shè)A是E的子集，并包含于G的某一最小生成樹(shù)中。設(shè)C=(Vc,Ec)為森林GA=(V,A) 的一個(gè)連通分支。如果邊是連接C和Ga中其他某聯(lián)通分支的一條輕邊，則(u,v)對(duì)集合A來(lái)說(shuō)是安全.
在Kruskal(
克魯斯卡爾)算法和Prim(普里姆)算法
在Kruskal算法中，集合A是一個(gè)森林，加入集合A中的安全邊總是圖中連接兩個(gè)不同聯(lián)通分支的最小權(quán)邊。在Prim算法中，集合A僅形成單棵樹(shù)，添加入集合A的安全邊總是連接樹(shù)與一個(gè)不在樹(shù)中的頂點(diǎn)的最小權(quán)邊。
Kruskal(
克魯斯卡爾)算法(O(ElgE))：
該算法找出森林中連接任意兩棵樹(shù)的所有邊中，具有最小權(quán)值的邊(u,v)作為安全邊，并把它添加到正在生長(zhǎng)的森林中。設(shè)C1和C2表示邊(u,v)連接的兩棵樹(shù)，因?yàn)?u,v)必是連接C1和其他某棵樹(shù)的一條輕邊，所以由上面推論可知，(u,v)對(duì)C1來(lái)說(shuō)是安全邊。Kruskal 算法同時(shí)也是一種貪心算法， 因?yàn)樵谒惴ǖ拿恳徊街校砑拥缴种械倪叺臋?quán)值都是盡可能小的。
下面是偽代碼:
MST-KRUSKAL(G,w)
A<--空集
for each vertex v 屬于 V[G]
do MAKE-SET(v)
sort the edges of E into nondecreasing order by weight w
for each edge(u,v)屬于E,taken in nondecreasing order by weight
do if FIND-SET(u)!=FIND-SET(v)
then A<--AU{(u,v)}
UNION(u,v)
return A
FIND-SET(u)返回包含u的集合中的一個(gè)代表元素。于是通過(guò)測(cè)試FIND-SET(u)是否等同于FIND-SET(v)，就可以確定頂點(diǎn)u和v是否屬于同一棵樹(shù)。通過(guò)過(guò)程UNION，可以實(shí)現(xiàn)樹(shù)與樹(shù)的合并。
Prim算法(O(ElgV))
Prim算法的特點(diǎn)是集合A中的邊總是形成單棵樹(shù)。樹(shù)從任意根頂點(diǎn)r開(kāi)始形成，并逐漸生成，直至該樹(shù)覆蓋了V中的所有頂點(diǎn)。在每一步，一條連接了樹(shù)A與Ga=(V,A)中某孤立頂點(diǎn)的輕邊被加入樹(shù)A中。由推論可知，該規(guī)則僅加入對(duì)A安全的邊，因此當(dāng)算法終止時(shí)，A中的邊形成了一棵最小生成樹(shù)。因此每次添加到樹(shù)中的邊都是使樹(shù)的權(quán)盡可能小的邊，因此，上述策略也是“貪心“的。
偽代碼如下：
MST-PRIM(G,w,r)
for each u 屬于V[G]
do key[u] <--空集
n[u]<--NIL
key[r]<--0
Q<--V[G]
while Q!=空集
do u<---EXTRACT-MIN(Q)
for each v屬于Adj[u]
do if v 屬于Q and w(u,v)<key[v]
then n[u]<---u
key[v]<--w(u,v)
參考：算法導(dǎo)論