最小生成树~ Prim And Kruscal

两个算法都是贪心算法。他代表在每一步必须在多个可能的选择中选择一种。贪心算法推荐选择在当前看来最好的选择。
最小生成树描述的问题是在连通无向图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;
}