詳解次小生成樹(shù)以及相關(guān)的C++求解方法
次小生成樹(shù)的定義
設(shè) G=(V,E,w)是連通的無(wú)向圖,T 是圖G 的一個(gè)最小生成樹(shù)。如果有另一棵樹(shù)T1,滿(mǎn)
足不存在樹(shù)T',ω(T')<ω(T1) ,則稱(chēng)T1是圖G的次小生成樹(shù)。
求解次小生成樹(shù)的算法
約定:由T 進(jìn)行一次可行交換得到的新的生成樹(shù)所組成的集合,稱(chēng)為樹(shù)T的鄰集,記為N(T)。
定理 3:設(shè)T是圖G的最小生成樹(shù),如果T1滿(mǎn)足ω(T1)=min{ω(T')| T'∈N(T)},則T1是G
的次小生成樹(shù)。
證明:如果 T1 不是G 的次小生成樹(shù),那么必定存在另一個(gè)生成樹(shù)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 的生成樹(shù),且均屬于N(T),所以ω(aj)≥ω(bij),
所以ω(T')≥ω(T+aj-bij)≥ω(T1),故矛盾。所以T1是圖G 的次小生成樹(shù)。
通過(guò)上述定理,我們就有了解決次小生成樹(shù)問(wèn)題的基本思路。
首先先求該圖的最小生成樹(shù)T。時(shí)間復(fù)雜度O(Vlog2V+E)
然后,求T的鄰集中權(quán)值和最小的生成樹(shù),即圖G 的次小生成樹(shù)。
如果只是簡(jiǎn)單的枚舉,復(fù)雜度很高。首先枚舉兩條邊的復(fù)雜度是O(VE),再判斷該交換是否
可行的復(fù)雜度是O(V),則總的時(shí)間復(fù)雜度是O(V2E)。這樣的算法顯得很盲目。經(jīng)過(guò)簡(jiǎn)單的
分析不難發(fā)現(xiàn),每加入一條不在樹(shù)上的邊,總能形成一個(gè)環(huán),只有刪去環(huán)上的一條邊,才能
保證交換后仍然是生成樹(shù),而刪去邊的權(quán)值越大,新得到的生成樹(shù)的權(quán)值和越小。我們可以
以此將復(fù)雜度降為O(VE)。這已經(jīng)前進(jìn)了一大步,但仍不夠好。
回顧上一個(gè)模型——最小度限制生成樹(shù),我們也曾面臨過(guò)類(lèi)似的問(wèn)題,并且最終采用動(dòng)態(tài)規(guī)
劃的方法避免了重復(fù)計(jì)算,使得復(fù)雜度大大降低。對(duì)于本題,我們可以采用類(lèi)似的思想。首
先做一步預(yù)處理,求出樹(shù)上每?jī)蓚€(gè)結(jié)點(diǎn)之間的路徑上的權(quán)值最大的邊,然后,枚舉圖中不在
樹(shù)上的邊,有了剛才的預(yù)處理,我們就可以用O(1)的時(shí)間得到形成的環(huán)上的權(quán)值最大的邊。
如何預(yù)處理呢?因?yàn)檫@是一棵樹(shù),所以并不需要什么高深的算法,只要簡(jiǎn)單的BFS 即可。
預(yù)處理所要的時(shí)間復(fù)雜度為O(V2)。
這樣,這一步時(shí)間復(fù)雜度降為O(V2)。
綜上所述,次小生成樹(shù)的時(shí)間復(fù)雜度為O(V2)。
練習(xí)
題目:
題目描述:
最小生成樹(shù)大家都已經(jīng)很了解,次小生成樹(shù)就是圖中構(gòu)成的樹(shù)的權(quán)值和第二小的樹(shù),此值也可能等于最小生成樹(shù)的權(quán)值和,你的任務(wù)就是設(shè)計(jì)一個(gè)算法計(jì)算圖的最小生成樹(shù)。
輸入:
存在多組數(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。
輸出:
輸出次小生成樹(shù)的值,如果不存在輸出-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代碼(注釋寫(xiě)的比較清楚):
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 100000 int father[210]; // 并查集 int visit[210]; // 記錄最小生成樹(shù)用到的邊的下標(biāo) int windex; // 記錄最小生成樹(shù)用到邊的數(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; } /** * 求最小生成樹(shù) */ 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; } /** * 求次小生成樹(shù) */ 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(); // 求次小生成樹(shù) 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) { // 無(wú)法生成最小生成樹(shù) printf("-1\n"); continue; } else { min = secMinTree(points, m, n); printf("%d\n", min); } free(points); } return 0; }
- C++實(shí)現(xiàn)二叉樹(shù)遍歷序列的求解方法
- C++實(shí)現(xiàn)第K順序統(tǒng)計(jì)量的求解方法
- 使用C++遞歸求解跳臺(tái)階問(wèn)題
- 約瑟夫問(wèn)題的Python和C++求解方法
- C++ 自定義棧實(shí)現(xiàn)迷宮求解
- C++通過(guò)自定義函數(shù)求一元二次方程的根
- c++編寫(xiě)簡(jiǎn)單的計(jì)算器程序
- 簡(jiǎn)單實(shí)現(xiàn)C++復(fù)數(shù)計(jì)算器
- C/C++經(jīng)典實(shí)例之模擬計(jì)算器示例代碼
- C++實(shí)現(xiàn)的求解多元一次方程示例
相關(guān)文章
C++編程中break語(yǔ)句和continue語(yǔ)句的學(xué)習(xí)教程
這篇文章主要介紹了C++編程中break語(yǔ)句和continue語(yǔ)句的學(xué)習(xí)教程,break和continue是C++循環(huán)控制中的基礎(chǔ)語(yǔ)句,需要的朋友可以參考下2016-01-01C++ 基類(lèi)指針和子類(lèi)指針相互賦值的實(shí)現(xiàn)方法
下面小編就為大家?guī)?lái)一篇C++ 基類(lèi)指針和子類(lèi)指針相互賦值的實(shí)現(xiàn)方法。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-12-12C語(yǔ)言static修飾函數(shù)詳細(xì)解析
以下是對(duì)C語(yǔ)言中的static修飾函數(shù)進(jìn)行了詳細(xì)的分析介紹,需要的朋友可以過(guò)來(lái)參考下2013-08-08c++?qt自定義搜索編輯框的實(shí)現(xiàn)方法
這篇文章主要介紹了c++?qt自定義搜索編輯框,通過(guò)自定義QLineEdit,在編輯框里添加布局,將按鈕設(shè)置在右邊,當(dāng)點(diǎn)擊按鈕搜索按鈕時(shí)發(fā)送信號(hào)到主界面做相應(yīng)的操作,需要的朋友可以參考下2022-03-03Matlab實(shí)現(xiàn)帶豎線散點(diǎn)的核密度圖的繪制
核密度估計(jì)是用于估計(jì)隨機(jī)變量概率密度函數(shù)的一種非參數(shù)方法。核密度圖不失為一種用來(lái)觀察連續(xù)型變量分布的有效方法。本文將用Matlab實(shí)現(xiàn)帶豎線散點(diǎn)的核密度圖的繪制,感興趣的可以了解一下2022-08-08C語(yǔ)言實(shí)現(xiàn)輸入兩個(gè)數(shù)字將其按從小到大輸出的方法
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)輸入兩個(gè)數(shù)字將其按從小到大輸出的方法,本文通過(guò)代碼講解的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-04-04