hdu 1233 还是畅通工程(最小生成树的Prim和Kruskal两种算法的c++实现)(prim算法详解)...
赤裸裸滴最小生成樹(shù)（MST），剛學(xué)的玩意，用兩種方法熟練一下。（都是greedy)
Kruskal方法：先對(duì)邊按照代價(jià)非遞減排序，再不斷添加邊且不產(chǎn)生環(huán)路，當(dāng)邊數(shù)=點(diǎn)數(shù)-1結(jié)束。判斷加入（v，w）是否會(huì)產(chǎn)生環(huán)路，可以用并查集，如果檢查v和w在同一集合中，說(shuō)明這兩個(gè)點(diǎn)已經(jīng)連通，加入邊（v, w）就會(huì)產(chǎn)生環(huán)路。Kruskal算法總時(shí)間復(fù)雜度O(eloge).
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 const int MAXN = 5050; 5 int n, father[MAXN], m; //m邊數(shù) 6 struct Edge 7 { 8 int x, y, length; 9 bool operator<(const Edge a) const 10 { 11 return length < a.length; 12 } 13 }; 14 Edge e[MAXN]; 15 void Init(int *a) 16 { 17 for (int i = 1; i <= n; ++i) 18 father[i] = i; 19 } 20 int Find(int x) 21 { 22 if (x != father[x]) 23 father[x] = Find(father[x]); 24 return father[x]; 25 } 26 void Union(int x, int y) 27 { 28 int fx = Find(x), fy = Find(y); 29 if (fx != fy) 30 father[fx] = fy; 31 } 32 int Kruskal() 33 { 34 std::sort(e, e + m); 35 Init(father); 36 int sum = 0; 37 for (int i = 0; i < m; ++i) 38 if (Find(e[i].x) != Find(e[i].y)) 39 { 40 Union(e[i].x, e[i].y); 41 sum += e[i].length; 42 } 43 return sum; 44 } 45 int main() 46 { 47 while (scanf("%d", &n) != EOF && n) 48 { 49 m = n * (n - 1) / 2; 50 for (int i = 0; i < m; ++i) 51 scanf("%d %d %d", &e[i].x, &e[i].y, &e[i].length); 52 printf("%d\n", Kruskal()); 53 } 54 return 0; 55 }Prim算法：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 const int MAXN = 101; 5 const int INF = INT_MAX; 6 int n, m, visited[MAXN], dist[MAXN]; //dist[i]記錄i到與i鄰接且未被訪問(wèn)的點(diǎn)的最小權(quán)值 7 int map[MAXN][MAXN]; 8 int Prim(int n) 9 { 10 memset(visited, 0, sizeof(visited)); 11 visited[1] = 1; 12 dist[1] = INF; 13 for (int i = 2; i <= n; ++i) 14 dist[i] = map[1][i]; 15 int min, pos, sum = 0; 16 for (int i = 2; i <= n; ++i) //加入剩下的n-1個(gè)點(diǎn) 17 { 18 min = INF; 19 for (int j = 1; j <= n; ++j) 20 if (!visited[j] && dist[j] < min) 21 { 22 min = dist[j]; 23 pos = j; 24 } 25 sum += min; //或者sum += dist[pos]; 26 visited[pos] = 1; 27 for (int j = 1; j <= n; ++j) //刷新最小權(quán)值 28 if (!visited[j] && map[pos][j] < dist[j]) 29 dist[j] = map[pos][j]; 30 } 31 return sum; 32 } 33 int main() 34 { 35 while (scanf("%d", &n) != EOF && n) 36 { 37 m = n * (n - 1) / 2; 38 int x, y, len; 39 for (int i = 0; i < m; ++i) //建圖 40 { 41 scanf("%d %d %d", &x, &y, &len); 42 map[x][y] = map[y][x] = len; 43 } 44 for (int i = 0; i <= n; ++i) 45 map[i][i] = INF; 46 printf("%d\n", Prim(n)); 47 } 48 return 0; 49 }?
還不是很熟悉，貼一個(gè)資料先學(xué)一下。
假設(shè)G＝（V，E）為一網(wǎng)圖，其中V 為網(wǎng)圖中所有頂點(diǎn)的集合，E 為網(wǎng)圖中所有帶權(quán)邊的集合。設(shè)置兩個(gè)新的集合U 和T，其中集合U 用于存放G 的最小生成樹(shù)中的頂點(diǎn)，集合T 存放G 的最小生成樹(shù)中的邊。令集合U 的初值為U＝{u1}（假設(shè)構(gòu)造最小生成樹(shù)時(shí)，從頂點(diǎn)u1 出發(fā)），集合T 的初值為T(mén)＝{}。Prim 算法的思想是，從所有u∈U，v∈V－U 的邊中，選取具有最小權(quán)值的邊（u，v），將頂點(diǎn)v 加入集合U 中，將邊（u，v）加入集合T 中，如此不斷重復(fù)，直到U＝V 時(shí)，最小生成樹(shù)構(gòu)造完畢，這時(shí)集合T 中包含了最小生成樹(shù)的所有邊。
Prim 算法可用下述過(guò)程描述，其中用wuv 表示頂點(diǎn)u 與頂點(diǎn)v 邊上的權(quán)值。
（1）U＝{u1},T={};
（2）while (U≠V)do
(u，v)＝min{wuv；u∈U，v∈V－U }
T＝T＋{(u，v)}
U＝U＋{v}
（3）結(jié)束。
圖8.23 (a)所示的一個(gè)網(wǎng)圖，按照Prim 方法，從頂點(diǎn)1 出發(fā)，該網(wǎng)的最小生成樹(shù)的產(chǎn)生過(guò)程如圖8.23 (b)、(c)、(d)、(e)、(f)和(g)所示。
為實(shí)現(xiàn)Prim 算法，需設(shè)置兩個(gè)輔助一維數(shù)組lowcost 和closevert，其中l(wèi)owcost 用來(lái)保存集合V－U 中各頂點(diǎn)與集合U 中各頂點(diǎn)構(gòu)成的邊中具有最小權(quán)值的邊的權(quán)值；數(shù)組closevertex 用來(lái)保存依附于該邊的在集合U 中的頂點(diǎn)。假設(shè)初始狀態(tài)時(shí)，U＝{u1}(u1 為出發(fā)的頂點(diǎn))，這時(shí)有l(wèi)owcost[0]=0，它表示頂點(diǎn)u1 已加入集合U 中，數(shù)組lowcost 的其它各分量的值是頂點(diǎn)u1 到其余各頂點(diǎn)所構(gòu)成的直接邊的權(quán)值。然后不斷選取權(quán)值最小的邊（ui，uk）（ui∈U，uk∈V－U），每選取一條邊，就將lowcost（k）置為0，表示頂點(diǎn)uk 已加入集合U 中。由于頂點(diǎn)uk 從集合V－U 進(jìn)入集合U 后，這兩個(gè)集合的內(nèi)容發(fā)生了變化，就需依據(jù)具體情況更新數(shù)組lowcost 和closevertex 中部分分量的內(nèi)容。最后closevertex 中即為所建立的最小生成樹(shù)。
當(dāng)無(wú)向網(wǎng)采用二維數(shù)組存儲(chǔ)的鄰接矩陣存儲(chǔ)時(shí)，Prim 算法的C 語(yǔ)言實(shí)現(xiàn)為：
先從某一點(diǎn)開(kāi)始，把這一個(gè)開(kāi)始的點(diǎn)放于聲明的一個(gè)數(shù)組或者集合里，表明這一點(diǎn)已經(jīng)被訪問(wèn)過(guò)。然后再?gòu)挠嘞碌膎-1個(gè)點(diǎn)里去找那個(gè)權(quán)值最小的點(diǎn)并記錄該點(diǎn)的位置然后再加上這一點(diǎn)的權(quán)值，同時(shí)將該點(diǎn)放于集合里表明該點(diǎn)已初訪問(wèn)。再更新權(quán)值
void Prim（int gm[][MAXNODE]，int n，int closevertex[]） {/*用Prim 方法建立有n 個(gè)頂點(diǎn)的鄰接矩陣存儲(chǔ)結(jié)構(gòu)的網(wǎng)圖gm 的最小生成樹(shù)*/ /*從序號(hào)為0 的頂點(diǎn)出發(fā)；建立的最小生成樹(shù)存于數(shù)組closevertex 中*/int lowcost[100],mincost;int i,j,k;for (i=1;i<n;i++) /*初始化*/{lowcost[i]=gm[0][i];closevertex[i]=0;}lowcost[0]=0; /*從序號(hào)為0 的頂點(diǎn)出發(fā)生成最小生成樹(shù)*/closevertex[0]=0;for (i=1;i<n;i++) /*尋找當(dāng)前最小權(quán)值的邊的頂點(diǎn)*/{mincost=MAXCOST; /*MAXCOST 為一個(gè)極大的常量值*/j=1;k=1;while (j<n){ if (lowcost[j]<mincost && lowcost[j]!=0){ mincost=lowcost[j];k=j;}j++;}printf(“頂點(diǎn)的序號(hào)＝%d 邊的權(quán)值＝%d\n”,k,mincost);lowcost[k]=0;for (j=1;j<n;j++) /*修改其它頂點(diǎn)的邊的權(quán)值和最小生成樹(shù)頂點(diǎn)序號(hào)*/if (gm[k][j]<lowcost[j]){ lowcost[j]=gm[k][j];closevertex[j]=k;}} }?
算法8.14
圖8.24 給出了在用上述算法構(gòu)造網(wǎng)圖8.23 (a)的最小生成樹(shù)的過(guò)程中，數(shù)組closevertex、lowcost 及集合U，V－U 的變化情況，讀者可進(jìn)一步加深對(duì)Prim 算法的了解。
在Prim 算法中，第一個(gè)for 循環(huán)的執(zhí)行次數(shù)為n－1，第二個(gè)for 循環(huán)中又包括了一個(gè)while 循環(huán)和一個(gè)for 循環(huán)，執(zhí)行次數(shù)為2(n-1)2，所以Prim 算法的時(shí)間復(fù)雜度為O(n2)。
關(guān)于prim算法
先把有的點(diǎn)放于一個(gè)集合（或者數(shù)組）里，這個(gè)集合里存放的是所有走過(guò)的點(diǎn)。初始值為0或者false表示還沒(méi)有點(diǎn)
聲明一個(gè)一維數(shù)組用于記錄各點(diǎn)的權(quán)值[可理解為起始點(diǎn)到目標(biāo)點(diǎn)的距離]，
聲明一個(gè)二維數(shù)組用于記錄某點(diǎn)到某一點(diǎn)的權(quán)值，如果這兩點(diǎn)不可達(dá)到，則設(shè)置為無(wú)窮大
具體執(zhí)行過(guò)程：
先從某一點(diǎn)開(kāi)始，把這一個(gè)開(kāi)始的點(diǎn)放于聲明的一個(gè)數(shù)組或者集合里，表明這一點(diǎn)已經(jīng)被訪問(wèn)過(guò)。然后再?gòu)挠嘞碌膎-1個(gè)點(diǎn)里去找那個(gè)權(quán)值最小的點(diǎn)并記錄該點(diǎn)的位置然后再加上這一點(diǎn)的權(quán)值，同時(shí)將該點(diǎn)放于集合里表明該點(diǎn)已初訪問(wèn)。再更新權(quán)值
再看下圖，從下圖分析：
1、
先選取一個(gè)點(diǎn)作起始點(diǎn)，然后選擇它鄰近的權(quán)值最小的點(diǎn)（如果有多個(gè)與其相連的相同最小權(quán)值的點(diǎn)，隨便選取一個(gè)）。如1作為起點(diǎn)。
isvisited[1]=1;?? //表明把1加進(jìn)來(lái)說(shuō)明是已經(jīng)訪問(wèn)過(guò)
pos=1; //記錄該位置
//用dist[]數(shù)組不斷刷新最小權(quán)值，dist[i](0<i<=點(diǎn)數(shù))的值為：i點(diǎn)到鄰近點(diǎn)（未被標(biāo)記）的最小距離。
dist[1]=0;? //起始點(diǎn)i到鄰近點(diǎn)的最小距離為0
dist[2]=map[pos][2]=4;
dist[3]=map[pos][3]=2;
dist[4]==map[pos][4]=3;
dist[5]=map[pos][5]=MaxInt;? //無(wú)法直達(dá)
dist[6]=map[pos][6]=MaxInt;
?
2、
再在伸延的點(diǎn)找與它鄰近的兩者權(quán)值最小的點(diǎn)。
//dist[]以3作當(dāng)前位置進(jìn)行更新
isvisited[3]=1;
pos=3;
dist[1]=0;?? //已標(biāo)記，不更新
dist[2]=map[pos][2]=4;??//比5小，不更新
dist[3]=2;? //已標(biāo)記，不更新
dist[4]=map[pos][4]=3;?? //比1大，更新
dist[5]=map[pos][5]=MaxInt;
dist[6]=map[pos][6]=MaxInt;
?
3、最后的結(jié)果:
?
當(dāng)所有點(diǎn)都連同后，結(jié)果最生成樹(shù)如上圖所示。
所有權(quán)值相加就是最小生成樹(shù)，其值為2+1+2+4+3=12。
prim算法的實(shí)現(xiàn)：
[cpp]?view plaincopyprint??
轉(zhuǎn)載于:https://www.cnblogs.com/PegasusWang/archive/2013/04/29/3050783.html
總結(jié)
以上是生活随笔為你收集整理的hdu 1233 还是畅通工程(最小生成树的Prim和Kruskal两种算法的c++实现)(prim算法详解)...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： Verilog代码风格
- 下一篇： 每日一水：HDOJ 1408 盐水的故事