快捷導(dǎo)航

詳解次小生成樹以及相關(guān)的C++求解方法

更新時(shí)間：2015年08月07日 11:19:30 作者：zinss26914

這篇文章主要介紹了詳解次小生成樹以及相關(guān)的C++求解方法,文中的練習(xí)示例采用了kruskal算法通過C++進(jìn)行求解,需要的朋友可以參考下

次小生成樹的定義
設(shè) G=(V,E,w)是連通的無向圖，T 是圖G 的一個(gè)最小生成樹。如果有另一棵樹T1，滿
足不存在樹T',ω（T'）<ω（T1），則稱T1是圖G的次小生成樹。

求解次小生成樹的算法
約定：由T 進(jìn)行一次可行交換得到的新的生成樹所組成的集合，稱為樹T的鄰集,記為N(T)。
定理 3：設(shè)T是圖G的最小生成樹，如果T1滿足ω(T1)=min{ω(T')| T'∈N(T)},則T1是G
的次小生成樹。
證明：如果 T1 不是G 的次小生成樹，那么必定存在另一個(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。根據(jù)引理1 知，存在一
個(gè)排列bi1,bi2,……,bit，使得T+aj-bij仍然是G 的生成樹，且均屬于N(T),所以ω(aj)≥ω(bij)，
所以ω(T')≥ω(T+aj-bij)≥ω(T1)，故矛盾。所以T1是圖G 的次小生成樹。
通過上述定理，我們就有了解決次小生成樹問題的基本思路。
首先先求該圖的最小生成樹T。時(shí)間復(fù)雜度O(Vlog2V+E)
然后，求T的鄰集中權(quán)值和最小的生成樹，即圖G 的次小生成樹。
如果只是簡(jiǎn)單的枚舉，復(fù)雜度很高。首先枚舉兩條邊的復(fù)雜度是O(VE)，再判斷該交換是否
可行的復(fù)雜度是O(V)，則總的時(shí)間復(fù)雜度是O(V2E)。這樣的算法顯得很盲目。經(jīng)過簡(jiǎn)單的
分析不難發(fā)現(xiàn)，每加入一條不在樹上的邊，總能形成一個(gè)環(huán)，只有刪去環(huán)上的一條邊，才能
保證交換后仍然是生成樹，而刪去邊的權(quán)值越大，新得到的生成樹的權(quán)值和越小。我們可以
以此將復(fù)雜度降為O(VE)。這已經(jīng)前進(jìn)了一大步，但仍不夠好。
回顧上一個(gè)模型——最小度限制生成樹，我們也曾面臨過類似的問題，并且最終采用動(dòng)態(tài)規(guī)
劃的方法避免了重復(fù)計(jì)算，使得復(fù)雜度大大降低。對(duì)于本題，我們可以采用類似的思想。首
先做一步預(yù)處理，求出樹上每?jī)蓚€(gè)結(jié)點(diǎn)之間的路徑上的權(quán)值最大的邊，然后，枚舉圖中不在
樹上的邊，有了剛才的預(yù)處理，我們就可以用O(1)的時(shí)間得到形成的環(huán)上的權(quán)值最大的邊。
如何預(yù)處理呢？因?yàn)檫@是一棵樹，所以并不需要什么高深的算法，只要簡(jiǎn)單的BFS 即可。
預(yù)處理所要的時(shí)間復(fù)雜度為O(V2)。
這樣，這一步時(shí)間復(fù)雜度降為O(V2)。
綜上所述，次小生成樹的時(shí)間復(fù)雜度為O(V2)。

練習(xí)
題目：

    題目描述：
    最小生成樹大家都已經(jīng)很了解，次小生成樹就是圖中構(gòu)成的樹的權(quán)值和第二小的樹，此值也可能等于最小生成樹的權(quán)值和，你的任務(wù)就是設(shè)計(jì)一個(gè)算法計(jì)算圖的最小生成樹。
    輸入：
    存在多組數(shù)據(jù)，第一行一個(gè)正整數(shù)t，表示有t組數(shù)據(jù)。
    每組數(shù)據(jù)第一行有兩個(gè)整數(shù)n和m（2<=n<=100），之后m行，每行三個(gè)正整數(shù)s，e，w，表示s到e的雙向路的權(quán)值為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]; // 記錄最小生成樹用到的邊的下標(biāo) 
  int windex; // 記錄最小生成樹用到邊的數(shù)量 
   
  typedef struct node { 
    int st, ed, w; 
  } node; 
   
  /** 
   * 預(yù)處理并查集數(shù)組 
   */ 
  void preProcess() 
  { 
    int i, len = sizeof(father) / sizeof(father[0]); 
   
    for (i = 0; i < len; i ++) { 
      father[i] = i; 
    } 
   
  } 
   
  /** 
   * kruskal使用貪心算法，將邊按權(quán)值從小到大排序 
   */ 
  int cmp(const void *p, const void *q) 
  { 
    const node *a = p; 
    const node *b = q; 
   
    return a->w - b->w; 
  } 
   
  /** 
   * 并查集尋找起始結(jié)點(diǎn)，路徑壓縮優(yōu)化 
   */ 
  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; 
  }

您可能感興趣的文章: