詳解次小生成樹和相干的C++求解辦法。本站提示廣大學習愛好者：（詳解次小生成樹和相干的C++求解辦法）文章只能為提供參考，不一定能成為您想要的結果。以下是詳解次小生成樹和相干的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;
}
