安全邊：在每一次迭代之前， A是某個最小生成樹的一個子集。在算法的每一步中，確定一條邊（u,v),使得將它加入集合A后，仍然不違反這個循環不等式，A U {(u,v)}仍然是某一個最小生成樹的子集。稱這樣的邊為A的安全邊。
識別安全邊的定理：設圖G=(V,E)是一個無向連通圖，并且在E上定義了一個具有實數值的加權函數w.設A是E的一個子集，它包含于G的某個最小生成樹中。設割(S,V-S)是G的任意一個不妨害A的割，且邊(u,v)是通過割(S,V-S)的一條輕邊，則邊(u,v)對集合A來說是安全的。
推論：設G=(V,E)是一個無向聯通圖，并且在E上定義了相應的實數值加權函數w.設A是E的子集，并包含于G的某一最小生成樹中。設C=(Vc,Ec)為森林GA=(V,A) 的一個連通分支。如果邊是連接C和Ga中其他某聯通分支的一條輕邊，則(u,v)對集合A來說是安全.
在Kruskal(
克魯斯卡爾)算法和Prim(普里姆)算法
在Kruskal算法中，集合A是一個森林，加入集合A中的安全邊總是圖中連接兩個不同聯通分支的最小權邊。在Prim算法中，集合A僅形成單棵樹，添加入集合A的安全邊總是連接樹與一個不在樹中的頂點的最小權邊。
Kruskal(
克魯斯卡爾)算法(O(ElgE))：
該算法找出森林中連接任意兩棵樹的所有邊中，具有最小權值的邊(u,v)作為安全邊，并把它添加到正在生長的森林中。設C1和C2表示邊(u,v)連接的兩棵樹，因為(u,v)必是連接C1和其他某棵樹的一條輕邊，所以由上面推論可知，(u,v)對C1來說是安全邊。Kruskal 算法同時也是一種貪心算法， 因為在算法的每一步中，添加到森林中的邊的權值都是盡可能小的。
下面是偽代碼:
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的集合中的一個代表元素。于是通過測試FIND-SET(u)是否等同于FIND-SET(v)，就可以確定頂點u和v是否屬于同一棵樹。通過過程UNION，可以實現樹與樹的合并。
Prim算法(O(ElgV))
Prim算法的特點是集合A中的邊總是形成單棵樹。樹從任意根頂點r開始形成，并逐漸生成，直至該樹覆蓋了V中的所有頂點。在每一步，一條連接了樹A與Ga=(V,A)中某孤立頂點的輕邊被加入樹A中。由推論可知，該規則僅加入對A安全的邊，因此當算法終止時，A中的邊形成了一棵最小生成樹。因此每次添加到樹中的邊都是使樹的權盡可能小的邊，因此，上述策略也是“貪心“的。
偽代碼如下：
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)
參考：算法導論