Prim:以貪心的思想求得最小生成樹： 把已建成的樹看成一個(gè)結(jié)點(diǎn)， 然后用貪心的方法每次添加距離最短的點(diǎn)。

以Poj1258為例：http://poj.org/problem?id=1258

?

1.樸素版本：鄰接矩陣, 無任何優(yōu)化,?O(n^2)

1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 #include <cmath> 7 using namespace std; 8 9 const int maxn = 100 + 2; 10 int map[maxn][maxn]; 11 bool vis[maxn]; 12 int dist[maxn]; 13 int n; 14 15 int Prim(int x) 16 { 17 int ret = 0, p = 0; 18 vis[x] = true; 19 dist[x] = 0; 20 21 for(int i = 1; i < n; i++) 22 { 23 for(int r = 1; r <= n; r++) 24 if(map[x][r]) 25 dist[r] = min(dist[r], map[x][r]); 26 27 for(int r = 1; r <= n; r++) 28 if(!vis[r]) 29 p = p ? (dist[p] < dist[r] ? p : r) : r; 30 31 ret += dist[p]; 32 x = p, p = 0; 33 vis[x] = true; 34 } 35 return ret; 36 } 37 38 int main() 39 { 40 //freopen("in.txt", "r", stdin); 41 42 while(~scanf("%d", &n)) 43 { 44 for(int i = 1; i <= n; i++) 45 for(int r = 1; r <= n; r++) 46 scanf("%d", &map[i][r]); 47 48 memset(vis, false, sizeof(vis)); 49 memset(dist, 0x7f, sizeof(dist)); 50 51 printf("%d\n", Prim(1)); 52 } 53 }

也沒什么可解釋的.

?

?

2.臨界矩陣， 優(yōu)先隊(duì)列優(yōu)化(堆同)， O(nlogn)

1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <algorithm> 6 #include <cmath> 7 #include <queue> 8 using namespace std; 9 10 const int maxn = 100 + 2; 11 priority_queue< pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q; 12 int map[maxn][maxn]; 13 bool vis[maxn]; 14 int dist[maxn]; 15 int n; 16 17 int Prim(int x) 18 { 19 memset(vis, false, sizeof(vis)); 20 memset(dist, 0x7f, sizeof(dist)); 21 int ret = 0; 22 dist[x] = 0; 23 24 while(!q.empty()) q.pop(); 25 26 for(int i = 1; i < n; i++) 27 { 28 vis[x] = true; 29 30 for(int r = 1; r <= n; r++) 31 if(dist[r] > map[x][r] && map[x][r] && !vis[r]) 32 dist[r] = map[x][r], q.push(make_pair(dist[r], r)); 33 34 while(!q.empty() && vis[q.top().second]) 35 q.pop(); 36 37 x = q.top().second; 38 ret += dist[x]; 39 } 40 return ret; 41 } 42 43 int main() 44 { 45 // freopen("in.txt", "r", stdin); 46 47 while(~scanf("%d", &n)) 48 { 49 for(int i = 1; i <= n; i++) 50 for(int r = 1; r <= n; r++) 51 scanf("%d", &map[i][r]); 52 53 printf("%d\n", Prim(1)); 54 } 55 56 57 }

<1>.pair<typename, pytename> p：是一種結(jié)構(gòu)體，只有兩個(gè)元素，<, >兩個(gè)typename 分別為兩個(gè)元素的類型

通過 p.first, p.second 分別訪問第一個(gè)元素和第二個(gè)元素。

<2>.memset(name, value, sizeof), 屬于 string.h 是字符數(shù)組的填充函數(shù)， 因?yàn)樽址鹀har類型為1字節(jié)，所以填充int數(shù)組時(shí)也是按單字節(jié)填充， 初始化時(shí)若每個(gè)字節(jié)的值過大， 會(huì)出現(xiàn)負(fù)數(shù)(整數(shù)存儲(chǔ)原理， 補(bǔ)碼。)

<3>?priority_queue< pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;為聲明小根堆(個(gè)人感覺優(yōu)先隊(duì)列和堆區(qū)分不用很明顯， 因?yàn)閮?nèi)部存儲(chǔ)結(jié)構(gòu)已經(jīng)不重要)， 相鄰的兩個(gè)相同左右尖括號(hào)要用空格隔開， 否則會(huì)組成左移右移運(yùn)算符, 此程序中時(shí)對(duì)pair進(jìn)行排序， 在排序時(shí)以第一個(gè)元素為關(guān)鍵字， 所以pair.first應(yīng)該存dist, 而不是點(diǎn)的編號(hào)。

<4>.補(bǔ)充一下。priority_queue< pair<int, int> >?q; 為聲明大根堆

?

3.鄰接表， 優(yōu)先隊(duì)列

1 #include <iostream> 2 #include <cstdlib> 3 #include <cstdio> 4 #include <cstring> 5 #include <queue> 6 using namespace std; 7 8 const int maxn = 10000 + 2, maxm = 100000 + 2; 9 #define pii pair<int, int> 10 #define fi first 11 #define se second 12 #define MP make_pair 13 14 priority_queue<pii, vector<pii >, greater<pii > > heap; 15 int n, m, dist[maxn], s, t; 16 bool vis[maxn]; 17 18 struct arc 19 { 20 int e, v; 21 arc *next; 22 arc(){} 23 arc(int e, int v, arc *next) : e(e), v(v), next(next){} 24 void *operator new(unsigned, void *p) {return p;} 25 }*head[maxn], mem[maxm * 2], *sp = mem; 26 27 inline void addarc(int x, int y, int v) 28 { 29 head[x] = new(sp++) arc(y, v, head[x]); 30 head[y] = new(sp++) arc(x, v, head[y]); 31 } 32 33 int Prim(int x) 34 { 35 memset(dist, 0x7f, sizeof(dist)); 36 dist[x] = 0; 37 int ans = 0; 38 for (int i = 1; i < n; i++) 39 { 40 vis[x] = true; 41 for (arc *p = head[x]; p; p = p -> next) 42 if (dist[p -> e] > p -> v) 43 dist[p -> e] = p -> v, heap.push(MP(dist[p -> e], p -> e)); 44 45 while (!heap.empty() && vis[heap.top().se]) heap.pop(); 46 47 x = heap.top().se; 48 ans += dist[x]; 49 } 50 return ans; 51 } 52 53 int main() 54 { 55 freopen("Prim.in", "r", stdin); 56 freopen("Prim.out", "w", stdout); 57 58 scanf("%d%d", &n, &m); 59 int a, b, c; 60 for (int i = 1; i <= m; i++) 61 scanf("%d%d%d", &a, &b, &c), addarc(a, b, c); 62 63 printf("%d\n", Prim(1)); 64 65 return fclose(stdin), fclose(stdout), 0; 66 }

1.前向星存儲(chǔ)圖，一種犧牲空間獲取時(shí)間的方法，在算法競(jìng)賽中的試用比較普遍的做法。

2.沒什么好解釋的了...

?

轉(zhuǎn)載于:https://www.cnblogs.com/QQ-1615160629/p/6275246.html

總結(jié)

以上是生活随笔為你收集整理的Prim算法的3个版本的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。