對于一個帶權的無向連通圖，其每個生成樹所有邊上的權值之和可能不同，我們把所有邊上權值之和最小的生成樹稱為圖的最小生成樹。
普里姆算法是以其中某一頂點為起點，逐步尋找各個頂點上最小權值的邊來構建最小生成樹。
其中運用到了回溯，貪心的思想。
----------2018年5月24日補：
#begin
根據定義我們可知，求一個圖的最小生成樹的時候，一定會將所有的點都連接起來，也就是說，我們從任何一個點出發都可以得到這個圖的最小生成樹，那么我這里暫定從0出發，尋找到和0相連的點中最小的權值，作為連接0這一個點的邊（如果有相同的最小權值，則視要求處理），將0這一個點設置為不可訪問，同時保存此時的連接點，將求到的這一個點做和0一樣相同的處理...處理出n個點就可以求得這個圖的最小生成樹了（如果不能處理出n個點，那么此圖的最小生成樹也就不存在）。
#end
廢話少說，直接上題吧！這些東西多練就好！
?
一、最小生成樹：
1
6
0 6 1 5 0 0
6 0 5 0 3 0
1 5 0 5 6 4
5 0 5 0 0 2
0 3 6 0 0 6
0 0 4 2 6 0 15
//Asimple
#include <stdio.h>
#include <iostream>
#include <string.h>using namespace std;
#define INF 0xffffff
const int maxn = 55;
int G[maxn][maxn];//建圖
int T, n;int prim()
{int Min, sum = 0;int adv[maxn]; //保存定點下標int lowc[maxn]; //保存權值adv[0] = lowc[0] = 0 ;//初始化for(int i=1; i<n; i++){lowc[i] = G[0][i];//先放入 第0行 的所有權值adv[i] = 0 ;}//構建過程for(int i=1; i<n; i++){Min = INF ;int j = 1 ;int k = 0 ;while( j < n ){if( lowc[j]!=0 && lowc[j]<Min){Min = lowc[j] ;k = j ;}j ++ ;}sum += G[adv[k]][k] ;//計算最小權值//printf("%d,%d",adv[k],k);//打印節點lowc[k] = 0 ;//逐行遍歷接下來的k個頂點for(int l=1; l<n; l++){if( lowc[l]!=0 && G[k][l] < lowc[l] ){lowc[l] = G[k][l] ;adv[l] = k ;}}}return sum ;
}int main()
{cin >> T ;while( T -- ){cin >> n ;for(int i=0; i<n; i++)for(int j=0; j<n; j++){cin >> G[i][j];if( G[i][j] == 0 && i!=j )G[i][j] = INF ;}cout << prim() << endl ;}return 0;
}
?二、判斷最小生成樹是否唯一
給出一個連通無向圖，請判斷其最小生成樹是否是唯一的。
定義1（生成樹）：給出一個連通無向圖G=（V，E），G的一顆生成樹被標記為T=（V，E），則具有以下性質：
1）V'=V；?
2）T是連通無回路的。
定義2（最小生成樹）：給出一個邊帶權的連通無向圖G=（V，E），G 的最小生成樹T=（v，E）是具有最小總耗費的生成樹。T的總耗費表示E' 中所有邊的權值的和。
第 一行給出一個整數t（１＜＝ｔ＜＝２０），表示測試用例數，每個測試用例表示一個圖，測試用例的第一行給出兩個整數ｎ，ｍ（１＜＝ｎ＜＝１００），分別表 示頂點和邊的數目，后面的ｍ行每行是一個三元組（ｘｉ，ｙｉ，ｗｉ），表示ｘｉ和ｙｉ通過權值為ｗｉ的邊相連。任意兩個節點間至多只有一條邊相連。
對于每個測試用例，如果ＭＳＴ是唯一的，輸出其總耗費；否則輸出字符串'Not Unique!'.?
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 3
Not Unique!
?
#include <stdio.h>
#include <iostream>
#include <string.h>using namespace std;
#define INF 0xffffff
const int maxn = 55;
int G[maxn][maxn];//建圖
int T, n, m, x, y, num;void prim()
{int Min, sum = 0;int adv[maxn]; //保存定點下標int lowc[maxn]; //保存權值bool flag = false ;adv[0] = lowc[0] = 0 ;//初始化for(int i=1; i<n; i++){lowc[i] = G[0][i];//先放入 第0行 的所有權值adv[i] = 0 ;}//構建過程for(int i=1; i<n; i++){Min = INF ;int j = 1 ;int k = 0 ;while( j < n ){if( lowc[j]!=0 && lowc[j]<=Min){if( lowc[j] == Min ) flag = true ;Min = lowc[j] ;k = j ;}j ++ ;}sum += G[adv[k]][k] ;//計算最小權值lowc[k] = 0 ;//逐行遍歷接下來的k個頂點for(int l=1; l<n; l++){if( lowc[l]!=0 && G[k][l] < lowc[l] ){lowc[l] = G[k][l] ;adv[l] = k ;}}}if( flag ) cout << "Not Unique!" << endl ;else cout << sum << endl ;
}int main()
{cin >> T ;while( T -- ){cin >> n >> m ;for(int i=0; i<n; i++)for(int j=0; j<n; j++){if( i == j ) G[i][j] = 0 ;else G[i][j] = INF ;}for(int i=0; i<m; i++){cin >> x >> y >> num ;G[x-1][y-1] = num ;G[y-1][x-1] = num ;}prim();}return 0;
}
2018年4月1日更正：
上面的代碼過不了? POJ 1679。謝謝指點~~? ?今天更改了下自己的程序。
| 18390068 | Asimple | 1679 | Accepted | 312K | 16MS | C++ | 1483B | 2018-04-01 20:08:48 |
//Asimple #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> using namespace std; #define INF 0xffffff typedef long long ll ; const int maxn = 100+5; int n, T, num, cnt, x, y, t, m, w; int Map[maxn][maxn];void prim() {int lowc[maxn];for(int i=1; i<=n; i++) lowc[i] = Map[1][i];int sum = 0;bool flag = false;for(int l=1; l<n; l++) {int Min = INF;int k = 0;for(int j=2; j<=n; j++) {if( lowc[j]!=0 && Min > lowc[j] ) {k = j;Min = lowc[j];}}if( Min == INF ) break; sum += Min;int cnt = 0;for(int i=1; i<=n; i++)if( Map[k][i] == lowc[k] )cnt ++;if( cnt > 1 ) {flag = true;break;}lowc[k] = 0;for(int i=2; i<=n; i++) {if( lowc[i] > Map[k][i] ) {lowc[i] = Map[k][i];}}}if( flag ) cout << "Not Unique!" << endl;else cout << sum << endl; }void input() {ios_base::sync_with_stdio(false);cin >> T;while( T -- ) {cin >> n >> m;for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) {Map[i][j] = i==j?0:INF;}}while( m -- ) {cin >> x >> y >> w;Map[x][y] = min(Map[x][y], w);Map[y][x] = Map[x][y];}prim();} }int main() {input();return 0; }
?
.)
