一、最小生成树

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。

二、Prim算法

* Prim算法：由一棵树“长大”“开枝散叶”得到最小生成树。

算法简述

1.输入：一个加权连通图，其中顶点集合为V，边集合为E；

2.初始化：V_new= {x}，其中x为集合V中的任一节点（起始点），E_new= {},为空；

3.重复下列操作，直到V_new= V：

1）.在集合E中选取权值最小的边<u, v>，其中u为集合V_new中的元素，而v不在V_new集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；

2）.将v加入集合V_new中，将<u, v>边加入集合E_new中；

4.输出：使用集合V_new和E_new来描述所得到的最小生成树。

1 void Prim(int m[][MAXV],int nv,int begin) 2 { 3     int closest[MAXV];//c[i]=k记录i在最小生成树中的前驱结点是k 4     int lowcost[MAXV];//l[i]=v记录了从节点i到已知树上任何一个节点的最小距离为v  5     int i,j,min,k; 6     for(i=0;i
      
        %d = %d\n",closest[k]+1,k+1,m[closest[k]][k]);25         26         lowcost[k]=0;//表明k已经在树上了 27         for(j=0;j

View Code

三、Kruskal算法

* Kruskal算法：由多棵树“枝蔓相连”得到最小生成树。

算法简述

假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：

1.先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。

2.之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；

3.反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。

4.依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。

//begin at 21:27#include
     
      #include
      
       #define MAXM 200000#define MAXN 5000typedef struct Edge{    int w,h,t;//weight,head,tail}Edge;Edge ed[MAXM+1];int n,m;int dad[MAXN+1];int myCmp(const void *a,const void *b){    Edge *c=(Edge *)a;    Edge *d=(Edge *)b;    return (c->w-d->w);}int findDad(int a)//by the way, merge the path{    int p=a;    int q;    while(dad[a]!=a)        a=dad[a];    while(dad[p]!=p)    {        q=p;        p=dad[p];        dad[q]=a;    }    return a;}void merge(int a,int b){    dad[findDad(a)]=findDad(b);}int Kruskal()//return the total weight of the minTree{    int i,temp;    scanf("%d%d",&n,&m);    for(i=0;i
       
        ed[i].t)        {            temp=ed[i].h;            ed[i].h=ed[i].t;            ed[i].t=temp;        }    }        qsort(ed,m,sizeof(ed[0]),myCmp);//sort the edges         int anssum=0;    for(i=1;i<=n;i++)        dad[i]=i;    i=0;    int countEdge=0;    while(countEdge

四、【扩展】最小瓶颈生成树

瓶颈生成树无向图G的一颗瓶颈生成树是这样的一颗生成树，它最大的边权值在G的所有生成树中是最小的。瓶颈生成树的值为T中最大权值边的权。

无向图的最小生成树一定是瓶颈生成树，但瓶颈生成树不一定是最小生成树。

例题：

五、【扩展】最小瓶颈路

摘自的blog，我在这里进行了一下阅读优化：

给定一个加权无向图，并给定无向图中两个结点u和v，求u到v的一条路径，使得路径上边的最大权值最小。这个问题可以稍微加强一下，即求很多对结点之间的最小瓶颈路。

【定理】无向图中，任意两个结点的最小瓶颈路肯定在最小生成树上。

因此对于最小瓶颈路问题，最普通的算法就是bfs和dfs，但这大多数时候都会超时。

对于第一个问题，我们可以先求出最小生成树，然后从结点u对最小生成树进行DFS直到访问到结点v，DFS过程中就可以求出最长边。这种方法非常简单，但是效率就不够高，如果结点对很多的话，我们每次都对最小生成树进行DFS就会很慢了（一次时间O(n)）。

1、时间高效率

当你要查询每对点与点之间的瓶颈路时，最好的方法是， 先把所有点之间的求出来，然后存放到一个数组中 （二维数组）（查询代价O(1)），于是这要求节点不能过多，否则只能一个一个求。

1）我们先把最小生成树看成是一颗有根树，并且找出一个根节点（任意），

2）然后再从这个根节点开始遍历，求点与点之间的最大边权。

怎么遍历呢？我们想到了dfs （经过优化的dfs），我们让节点只与被标记（已经被遍历的节点）的节点进行比较，这样就不会使每对节点都要被比较两次。

1 void dfs(int v) 2 { 3     for ( int u = 1; u <= n; ++u )  //这里还可以用邻接表来减少时间 4     { 5         if(!done[u] && p[u] == v)  //  done检查是否被标记 ， p是指u是不是v的父亲节点 6         { 7            done[u] = 1; 8            for ( int x = 1; x <= n; ++x ) 9                if (done[x] && x != u ) 10                {11                    maxbian[x][u] = maxbian[u][x] =  maxbian[x][v]>maxbian[u][v]?maxbian[x][v]:maxbian[u][v];12                }13            dfs(u);14         }15     }16 }

View Code

2、空间高效率

这是当不能存储所有节点之间的最大边权的情况下的算法，这个算法计算单条最小瓶颈路时，肯定优于上面那个算法， However，要求所有点与点之间的...时，就比上面那个算法更慢了。

这个算法充分地考虑了最小生成树是一颗树的性质：

1）先把其建立成一颗有根树（根是任意的）

2）然后求LCA（u，v）即可（倍增LCA可能更快，当然代码复杂度也提升，看情况需不需要吧）（查询一次的时间O(logn)）

1 int solve(int x , int y) 2 { 3     int m1 = -1 , m2 = -1;  //  初始化两个节点在遍历过程中的最大边权 4     if(f[x] > f[y])   //  当这两个节点深度不一样时 5     { 6         while(f[x]>f[y]) 7         { 8             if(m1 < dist[x])  m1 = dist[x];  //  改变最大边权 9             x = p[x]; //  向上走后的节点 ， 也就是其父亲节点10         }11     }12     else if(f[x] < f[y])13     {14         while(f[x] < f[y])15         {16             if(m2 < dist[y])  m2 = dist[y];17             y = p[y];18         }19     }20     while(x != y)  //  这时 ， 两个节点的深度已经一样了21     {22         if(m1 < dist[x])  m1= dist[x];  //  两个节点同时向上走 ， 直到两个节点相同时23         if(m2 < dist[y])  m2 = dist[y];24         x = p[x];25         y = p[y];26     }27     return m1>m2?m1:m2;  // 返回两个节点中的最大边权28 }

View Code

六、【扩展】Matrix-Tree定理

相关Blog——（【推荐】他介绍的更详细些）

矩阵一树定理(matrix-tree theorem)是一个计数定理.

若连通图G的邻接矩阵为A，将A的对角线(i,i)元素依次换为节点 i 的度d(i)，其余元素(i,j) (j!=i) 取Aij的相反数，所得矩阵记为M，

则M的每个代数余子式相等，且等于G的生成树的数目.这就是 矩阵一树定理.

——from Baidu

代数余子式

在一个n阶行列式D中,把元素aij (i,j=1,2,.....n)所在的行与列划去后，剩下的(n-1)^2个元素按照原来的次序组成的一个n-1阶行列式Mij,称为元素aij的余子式，

Mij带上符号(-1)^(i+j)称为aij的代数余子式,

记作Aij=(-1)^(i+j) Mij。

——from Baidu

n阶行列式的计算方法

设
是由排成n阶方阵形式的n²个数aij(i,j=1,2,...,n)确定的一个数，

则其值为n！项之和

——from Baidu