最小生成树的性质

MST性质：设G = (V,E)是连通带权图，U是V的真子集。假设(u,v)∈E,且u∈U,v∈V-U,且在全部这种边中，

(u,v)的权c[u][v]最小，那么一定存在G的一棵最小生成树，(u,v)为当中一条边。

构造最小生成树，要解决下面两个问题：
(1).尽可能选取权值小的边，但不能构成回路（也就是环）。
(2).选取n-1条恰当的边以连接网的n个顶点。

Prim算法的思想：

设G = (V,E)是连通带权图，V = {1,2,…,n}。先任选一点（一般选第一个点），首先置S = {1}，然后，仅仅要S是V的真子集，就选取满足条件i ∈S,j ∈V-S,且c[i][j]最小的边，将顶点j加入到S中。这个过程一直进行到S = V时为止。在这个过程中选取到的全部边恰好构成G的一棵最小生成树。

Prim算法代码     

以 hdu 1863为例 （）

#include
     
      #include
      
       #include
       
        #define N 100int n,m,map[N+5][N+5],v[N+5],low[N+5];int prim(){    int i,j,pos,min,s=0;    memset(v,0,sizeof(v));           //v[i]用来标记i是否已訪问，先初始化为0，表示都未訪问    v[1]=1;                         //先任选一点作为第一个点    pos=1;                          //pos用来标记当前选的点的下标    for(i=2;i<=n;i++)        low[i]=map[1][i];          //用low数组存已选点到其它点的权值    for(i=1;i
       
      
     

Kruskal算法思想

给定无向连同带权图G = (V,E),V = {1,2,...,n}。

（1）首先将G的n个顶点看成n个孤立的连通分支。将全部的边按权从小大排序。

（2）从第一条边開始，依边权递增的顺序检查每一条边。并依照下述方法连接两个不同的连通分支：当查看到第k条边(v,w)时，假设端点v和w各自是当前两个不同的连通分支T1和T2的端点是，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；假设端点v和w在当前的同一个连通分支中，就直接再查看k+1条边。这个过程一个进行到仅仅剩下一个连通分支时为止。此时，已构成G的一棵最小生成树。

Kruskal算法代码：

以 hdu 1863为例 （）

#include
     
      #include
      
       using namespace std;int f[105],n,m;struct stu{    int a,b,c;}t[5500];int cmp(struct stu x,struct stu y){    return x.c
      
     

注：若顶点数为n,边为e

prim算法适合稠密图，其时间复杂度为O(n^2)，其时间复杂度与边的数目无关，

而kruskal算法的时间复杂度为O(eloge)跟边的数目有关，适合稀疏图。