两个算法都是贪心算法。他代表在每一步必须在多个可能的选择中选择一种。贪心算法推荐选择在当前看来最好的选择。
最小生成树描述的问题是在连通无向图G=（V,E）中找到 E 的一个无环子集 T ，既能连接所有结点，又具有最小的权重，即
的值最小。由于T中没有回路，连通所有结点，因此T必然是一棵树，即生成树。
时间复杂度
对于Kruskal和Prim算法，使用普通的最小堆，时间复杂度可以很容易限制在O（ElgV）以内，但fibonacci堆可以将Prim算法运行时间改善为O（E+VlgV），适用于稠密图时效果更为显著。
通用伪代码在这里~：
Generic—MST(G,w)
A = ∅
while A does not form a spanning tree
find an edge(u,v) that is safe for A /*找到安全边*/
A = A U {(u,v)}
return A
Kruskal算法和Prim算法
Kruscal在所有连接森林中两棵不同树的边里面，找到权重最小的边（u,v），设C1和C2为边（u,v）所连接的两棵树，Kruscal显然是贪心算法，因为每次都选择一条权重最小的边加入到森林。
Kruskal的实现大概是这个过程：
MST—Kruskal(G,w)
A = ∅
for each vertex v ∈ G,V
Make-Set(v)
sort the edfes of G.E into nodecreasing order by weight w
for each edge(u,v)∈G,E, taken in nondecreasing order by weight
if Find-Set(v) ≠ Find-Set(v)
A = AU{(u,v)}
UNION(u,v)
return A
涉及到的并查集和最小堆的实现，为节省空间~所以只贴出Kruskal的核心部分
int Kruskal(LGraph G, LGraph MST)
{
int TotalWeight=0;
int Edge_collected = 0;
int NextEdge;
SetType VSet;/*顶点数组*/
Edge ESet;
InitializeVSet( VSet, G->Nv );/*初始化顶点并查集*/
ESet =(Edge)malloc(sizeof(struct ENode)*G->Ne);
InitializeESet(G, ESet);/*初始化最小堆*/
MST = CreateGraph( G->Nv );
NextEdge = G->Ne;
while( Edge_collected < G->Nv-1 ){
NextEdge = GetEdge(ESet, NextEdge);
if(NextEdge < 0)
break;
/*判断该边的加入是否构成回路*/
if ( CheckCycle( VSet, ESet[NextEdge].V1, ESet[NextEdge].V2 )==TRUE ) {
/* 将该边插入MST */
InsertEdge( MST, ESet+NextEdge );
TotalWeight += ESet[NextEdge].Weight; /* 累计权重 */
ECount++; /* 生成树中边数加1 */
}
}
if( Edge_collected < G->Nv-1 )
TotalWeight = -1;/*生成树不存在*/
return TotalWeight;
}
