安全边：在每一次迭代之前， 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)
参考：算法导论