亲宝软件园·资讯

展开

C++求解次小生成树 详解次小生成树以及相关的C++求解方法

zinss26914 人气:0
想了解详解次小生成树以及相关的C++求解方法的相关内容吗,zinss26914在本文为您仔细讲解C++求解次小生成树的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:C++,次小生成树,下面大家一起来学习吧。

次小生成树的定义
设 G=(V,E,w)是连通的无向图,T 是图G 的一个最小生成树。如果有另一棵树T1,满
足不存在树T',ω(T')<ω(T1) ,则称T1是图G的次小生成树。

求解次小生成树的算法
约定:由T 进行一次可行交换得到的新的生成树所组成的集合,称为树T的邻集,记为N(T)。
定理 3:设T是图G的最小生成树,如果T1满足ω(T1)=min{ω(T')| T'∈N(T)},则T1是G
的次小生成树。
证明:如果 T1 不是G 的次小生成树,那么必定存在另一个生成树T',T'=T 使得
ω(T)≤ω(T')<ω(T1),由T1的定义式知T不属于N(T),则
E(T')/E(T)={a1,a2
1,……,at},E(T)/E(T')={b1,b2,……,bt},其中t≥2。根据引理1 知,存在一
个排列bi1,bi2,……,bit,使得T+aj-bij仍然是G 的生成树,且均属于N(T),所以ω(aj)≥ω(bij),
所以ω(T')≥ω(T+aj-bij)≥ω(T1),故矛盾。所以T1是图G 的次小生成树。
通过上述定理,我们就有了解决次小生成树问题的基本思路。
首先先求该图的最小生成树T。时间复杂度O(Vlog2V+E)
然后,求T的邻集中权值和最小的生成树,即图G 的次小生成树。
如果只是简单的枚举,复杂度很高。首先枚举两条边的复杂度是O(VE),再判断该交换是否
可行的复杂度是O(V),则总的时间复杂度是O(V2E)。这样的算法显得很盲目。经过简单的
分析不难发现,每加入一条不在树上的边,总能形成一个环,只有删去环上的一条边,才能
保证交换后仍然是生成树,而删去边的权值越大,新得到的生成树的权值和越小。我们可以
以此将复杂度降为O(VE)。这已经前进了一大步,但仍不够好。
回顾上一个模型——最小度限制生成树,我们也曾面临过类似的问题,并且最终采用动态规
划的方法避免了重复计算,使得复杂度大大降低。对于本题,我们可以采用类似的思想。首
先做一步预处理,求出树上每两个结点之间的路径上的权值最大的边,然后,枚举图中不在
树上的边,有了刚才的预处理,我们就可以用O(1)的时间得到形成的环上的权值最大的边。
如何预处理呢?因为这是一棵树,所以并不需要什么高深的算法,只要简单的BFS 即可。
预处理所要的时间复杂度为O(V2)。
这样,这一步时间复杂度降为O(V2)。
综上所述,次小生成树的时间复杂度为O(V2)。

练习
题目:

    题目描述: 
    最小生成树大家都已经很了解,次小生成树就是图中构成的树的权值和第二小的树,此值也可能等于最小生成树的权值和,你的任务就是设计一个算法计算图的最小生成树。 
    输入: 
    存在多组数据,第一行一个正整数t,表示有t组数据。 
    每组数据第一行有两个整数n和m(2<=n<=100),之后m行,每行三个正整数s,e,w,表示s到e的双向路的权值为w。 
    输出: 
    输出次小生成树的值,如果不存在输出-1。 
    样例输入: 
    2 
    3 3 
    1 2 1 
    2 3 2 
    3 1 3 
    4 4 
    1 2 2 
    2 3 2 
    3 4 2 
    4 1 2 
    样例输出: 
    4 
    6 


ac代码(注释写的比较清楚):

   

 #include <stdio.h> 
  #include <stdlib.h> 
  #include <string.h> 
   
  #define MAX 100000 
   
  int father[210];  // 并查集 
  int visit[210]; // 记录最小生成树用到的边的下标 
  int windex; // 记录最小生成树用到边的数量 
   
  typedef struct node { 
    int st, ed, w; 
  } node; 
   
  /** 
   * 预处理并查集数组 
   */ 
  void preProcess() 
  { 
    int i, len = sizeof(father) / sizeof(father[0]); 
   
    for (i = 0; i < len; i ++) { 
      father[i] = i; 
    } 
   
  } 
   
  /** 
   * kruskal使用贪心算法,将边按权值从小到大排序 
   */ 
  int cmp(const void *p, const void *q) 
  { 
    const node *a = p; 
    const node *b = q; 
   
    return a->w - b->w; 
  } 
   
  /** 
   * 并查集寻找起始结点,路径压缩优化 
   */ 
  int findParent(int x) 
  { 
    int parent; 
   
    if (x == father[x]) { 
      return x; 
    } 
   
    parent = findParent(father[x]); 
    father[x] = parent; 
     
    return parent; 
  } 
   
  /** 
   * 求最小生成树 
   */ 
  int minTree(node *points, int m, int n) 
  { 
    preProcess(); 
   
    int i, count, flag, pa, pb; 
   
    for (i = count = flag = windex = 0; i < m; i ++) { 
      pa = findParent(points[i].st); 
      pb = findParent(points[i].ed); 
       
      if (pa != pb) { 
        visit[windex ++] = i; 
        father[pa] = pb; 
        count ++; 
      } 
   
      if (count == n - 1) { 
        flag = 1; 
        break; 
      } 
    } 
   
    return flag; 
  } 
   
  /** 
   * 求次小生成树 
   */ 
  int secMinTree(node *points, int m, int n) 
  { 
    int i, j, min, tmp, pa, pb, count, flag; 
   
    for (i = 0, min = MAX; i < windex; i ++) { 
      preProcess(); 
   
      // 求次小生成树 
      for (j = count = tmp = flag = 0; j < m; j ++) { 
        if (j != visit[i]) { 
          pa = findParent(points[j].st); 
          pb = findParent(points[j].ed); 
   
          if (pa != pb) { 
            count ++; 
            tmp += points[j].w; 
            father[pa] = pb; 
          } 
   
          if (count == n - 1) { 
            flag = 1; 
            break; 
          } 
        } 
      } 
   
      if (flag && tmp < min)  min = tmp; 
    } 
   
    min = (min == MAX) ? -1 : min; 
   
    return min;  
  } 
   
   
  int main(void) 
  { 
    int i, t, n, m, flag, min; 
    node *points; 
   
    scanf("%d", &t); 
   
    while (t --) { 
      scanf("%d %d", &n, &m); 
   
      points = (node *)malloc(sizeof(node) * m);  
   
      for (i = 0; i < m; i ++) { 
        scanf("%d %d %d", &points[i].st, &points[i].ed, &points[i].w); 
      } 
   
      qsort(points, m, sizeof(points[0]), cmp); 
       
      flag = minTree(points, m, n); 
   
      if (flag == 0) {  // 无法生成最小生成树 
        printf("-1\n"); 
        continue; 
      } else { 
        min = secMinTree(points, m, n); 
        printf("%d\n", min); 
      } 
   
   
      free(points); 
    } 
   
    return 0; 
  } 



加载全部内容

相关教程
猜你喜欢
用户评论