本文共 6793 字，大约阅读时间需要 22 分钟。

kruskal:

1.思路

：设G=（V，E）是无向连通带权图，V={，…，n}；设最小生成树T=（V，TE），该树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），Kruskal算法将这n个顶点看成是n个孤立的连通分支。它首先将所有的边按权值从小到大排序，然后只要T中选中的边数不到n-1，就做如下的贪心选择：在边集E中选取权值最小的边（i，j），如果将边（i，j）加入集合TE中不产生回路（圈），则将边（i，j）加入边集TE中，即用边（i，j）将这两个连通分支合并连接成一个连通分支；否则继续选择下一条最短边。把边（i，j）从集合E中删去。继续上面的贪心选择，直到T中所有顶点都在同一个连通分支上为止。此时，选取到的n-1条边恰好构成G的一棵最小生成树T。 那么，怎样判断加入某条边后图T会不会出现回路呢？ 该算法对于手工计算十分方便，因为用肉眼可以很容易看到挑选哪些边能够避免构成回路（避圈法），但使用计算机程序来实现时，还需要一种机制来进行判断。Kruskal算法用了一个非常聪明的方法，就是运用集合避圈：如果所选择加入的边的起点和终点都在T的集合中，那么就可以断定一定会形成回路（圈）。其实就是我们”：边的两个结点不能属于同一集合。 步骤1：初始化。将图G的边集E中的所有边按权值从小到大排序，边集TE={ }，把每个顶点都初始化为一个孤立的分支，即一个顶点对应一个集合。

步骤2：在E中寻找权值最小的边（i，j）。 步骤3：如果顶点i和j位于两个不同连通分支，则将边（i，j）加入边集TE，并执行合并操作，将两个连通分支进行合并。 步骤4：将边（i，j）从集合E中删去，即E=E-{（i，j）}。 步骤5：如果选取边数小于n-1，转步骤2；否则，算法结束，生成最小生成树T。

伪码详解

（1）数据结构 int nodeset[N];//集合号数组

struct Edge {//边的存储结构 int u; int v; int w; }e[N*N]; （2）初始化 void Init(int n){ for(int i = 1; i <= n; i++) nodeset[i] = i;//每个结点赋值一个集合号} （3）对边进行排序 bool comp(Edge x, Edge y) { return x.w < y.w;//定义优先级，按边值进行升序排序}sort(e, e+m, comp);//调用系统排序函数 （4）合并集合 int Merge(int a, int b){ int p = nodeset[a];//p为a结点的集合号 int q = nodeset[b]; //q为b结点的集合号 if(p==q) return 0; //集合号相同，什么也不做，返回 for(int i=1;i<=n;i++)//检查所有结点，把集合号是q的全部改为p { if(nodeset[i]==q) nodeset[i] = p;//a的集合号赋值给b集合号 } return 1;}

kruskal完整代码

#include 
   
    #include 
    
     #include 
     
      using namespace std;const int N = 100;int nodeset[N];int n, m;struct Edge {
        int u;     int v;     int w;}e[N*N];bool comp(Edge x, Edge y) {
        return x.w < y.w;}void Init(int n){
        for(int i = 1; i <= n; i++)          nodeset[i] = i;}int Merge(int a, int b){
        int p = nodeset[a];      int q = nodeset[b];         if(p==q) return 0;           for(int i=1;i<=n;i++)//检查所有结点，把集合号是q的改为p     {
           if(nodeset[i]==q)           nodeset[i] = p;//a的集合号赋值给b集合号      }      return 1;  }  int Kruskal(int n){
          int ans = 0;          for(int i=0;i
      
       > n >> m;  Init(n);  cout <<"输入结点数u,v和边值w："<
       
        > e[i].u>> e[i].v >>e[i].w;  sort(e, e+m, comp);  int ans = Kruskal(n);  cout << "最小的花费是：" << ans << endl; return 0;}
       
      
     
    
   

1）时间复杂度：算法中，需要对边进行排序，若使用快速排序，执行次数为eloge，算法的时间复杂度为O(eloge)。而合并集合需要n-1次合并，每次为O(n)，合并集合的时间复杂度为O(n2)。

2）空间复杂度：算法所需要的辅助空间包含集合号数组 nodeset[n]，则算法的空间复杂度是O(n)。

6．算法优化拓展

该算法合并集合的时间复杂度为O(n2)，我们可以用并查集的思想优化，使合并集合的时间复杂度降为O(e*logn)，优化后的程序如下。

#include 
   
    #include 
    
     #include 
     
      using namespace std;const int N = 100;int father[N];int n, m;struct Edge {
        int u;     int v;     int w;}e[N*N];bool comp(Edge x, Edge y) {
        return x.w < y.w;//排序优先级，按边的权值从小到大}void Init(int n){
        for(int i = 1; i <= n; i++)          father[i] = i;//顶点所属集合号，初始化每个顶点一个集合号}int Find(int x) //找祖宗{
        if(x != father[x])     father[x] = Find(father[x]);//把当前结点到其祖宗路径上的所有结点的集合号改为祖宗集合号     return father[x]; //返回其祖宗的集合号}int Merge(int a, int b) //两结点合并集合号{
        int p = Find(a); //找a的集合号     int q = Find(b); //找b的集合号     if(p==q) return 0;     if(p > q)           father[p] = q;//小的集合号赋值给大的集合号     else           father[q] = p;     return 1;}int Kruskal(int n){
        int ans = 0;     for(int i=0;i
      
       > n >> m;       Init(n);       cout <<"输入结点数u，v和边值w："<
       
        >e[i].u>>e[i].v>>e[i].w;        sort(e, e+m, comp);       int ans = Kruskal(n);        cout << "最小的花费是：" << ans << endl;          return 0;}
       
      
     
    
   

输入结点数n和边数m：

7 12输入结点数u，v和边值w： 1 2 23 1 6 28 1 7 36 2 3 20 2 7 1 3 4 15 3 7 4 4 5 3 4 7 9 5 6 17 5 7 16 6 7 25 输出57

prim

步骤1：确定合适的数据结构。设置带权邻接矩阵C存储图G，如果图G中存在边（u，x），令C[u][x]等于边（u，x）上的权值，否则，C[u][x]=∞；bool数组s[]，如果s[i]=true，说明顶点i已加入集合U。

可以通过设置两个数组巧妙地解决这个问题，closest[j]表示V-U中的顶点j到集合U中的最邻近点，lowcost[j]表示V-U中的顶点j到集合U中的最邻近点的边值，即边（j,closest[j]）的权值。

（https://img-blog.csdnimg.cn/2021052415592813.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0,size_16,color_FFFFFF,t_70)

例如，在图中7号结点到U集合中的最邻近点是2，closest[7]=2，如图2-63所示。7号结点到最邻近点2的边值为1，即边（2，7）的权值，记为lowcost[7]=1，如图2-64所示。

只需要在V-U集合中找lowcost[ ]值最小的顶点即可。

步骤2：初始化。令集合U={u0}，u0∈V，并初始化数组closest[]、 lowcost[]和s[]。 步骤3：在V-U集合中找lowcost值最小的顶点t， 即lowcost[t]=min{lowcost[j]|j∈V-U}， 满足该公式的顶点t就是集合V-U中连接集合U的最邻近点。 步骤4：将顶点t加入集合U。 步骤5：如果集合V-U，算法结束，否则，转步骤6。 步骤6：对集合V-U中的所有顶点j，更新其lowcost[]和closest[]。cost [j]= C [t] [j]; closest [j] = t; }，转步骤3。 按照上述步骤，最终可以得到一棵权值之和最小的生成树。 更新公式： if（C[t] [j]<lowcost [j] ) { lowcost [j]= C [t] [j]; closest [j] = t; }，转步骤3。 按照上述步骤，最终可以得到一棵权值之和最小的生成树。

伪代码详解

（1）初始化。s[1]=true，初始化数组closest，除了u0外其余顶点最邻近点均为u0，表示V-U中的顶点到集合U的最临近点均为u0；初始代数组lowcost，u0到V-U中的顶点的边值，无边相连则为∞（无穷大）

　 s[u0] = true; //初始时，集合中U只有一个元素，即顶点u0 for(i = 1; i <= n; i++) { if(i != u0) //除u0之外的顶点 { lowcost[i] = c[u0][i]; //u0到其它顶点的边值 closest[i] = u0; //最邻近点初始化为u0 s[i] = false; //初始化u0之外的顶点不属于U集合，即属于V-U集合 } else lowcost[i] =0;}

2）在集合V-U中寻找距离集合U最近的顶点t。

int temp = INF; int t = u0; for(j = 1; j <= n; j++) //在集合中V-U中寻找距离集合U最近的顶点t { if((!s[j]) && (lowcost[j] < temp)) //!s[j] 表示j结点在V-U集合中 { t = j; temp = lowcost[j];

}

} if(t == u0) //找不到t，跳出循环 break; （3）更新lowcost和closest数组。 s[t] = true; //否则，t加入集合U for(j = 1; j <= n; j++) //更新lowcost和closest { if((!s[j]) && (c[t][j] < lowcost[j])) // !s[j] 表示j结点在V-U集合中 //t到j的边值小于当前的最邻近值 { lowcost[j] = c[t][j]; //更新j的最邻近值为t到j的边值 closest[j] = t; //更新j的最邻近点为t } }

prim完整代码

#include 
   
    using namespace std;const int INF = 0x3fffffff;const int N = 100;bool s[N];int closest[N];int lowcost[N];void Prim(int n, int u0, int c[N][N]) {
     //顶点个数n、开始顶点u0、带权邻接矩阵C[n][n]  //如果s[i]=true,说明顶点i已加入最小生成树  //的顶点集合U；否则顶点i属于集合V-U  //将最后的相关的最小权值传递到数组lowcost  s[u0] = true; //初始时，集合中U只有一个元素，即顶点u0  int i;  int j;  for(i = 1; i <= n; i++)//①  {
          if(i != u0)        {
               lowcost[i] = c[u0][i];            closest[i] = u0;            s[i] = false;       }       else            lowcost[i] =0;  }  for(i = 1; i <= n; i++)  //②  {
          int temp = INF;       int t = u0;       for(j = 1; j <= n; j++) //③在集合中V-u中寻找距离集合U最近的顶点t       {
               if((!s[j]) && (lowcost[j] < temp))            {
                   t = j;                temp = lowcost[j];           }       }      if(t == u0)         break;       //找不到t，跳出循环      s[t] = true;    //否则，讲t加入集合U      for(j = 1; j <= n; j++)  //④更新lowcost和closest      {
                    if((!s[j]) && (c[t][j] < lowcost[j]))          {
                 lowcost[j] = c[t][j];              closest[j] = t;          }      }    }}int main(){
       int n, c[N][N], m, u, v, w;    int u0;    cout <<"输入结点数n和边数m："<
    
     > n >> m;    int sumcost = 0;    for(int i = 1; i <= n; i++)        for(int j = 1; j <= n; j++)           c[i][j] = INF;    cout <<"输入结点数u，v和边值w："<
     
      > u >> v >> w;        c[u][v] = c[v][u] = w;    }    cout <<"输入任一结点u0："<
      
       > u0 ;    //计算最后的lowcos的总和，即为最后要求的最小的费用之和    Prim(n, u0, c);    cout <<"数组lowcost的内容为："<
      
     
    
   

转载地址：http://jtten.baihongyu.com/