Prim：

算法步驟：

1.任意結(jié)點(diǎn)開始（不妨設(shè)為v1）構(gòu)造最小生成樹： 2.首先把這個結(jié)點(diǎn)（出發(fā)點(diǎn)）包括進(jìn)生成樹里， 3.然后在那些其一個端點(diǎn)已在生成樹里、另一端點(diǎn)還未在生成樹里的所有邊中找出權(quán)最小的一條邊， 4.并把這條邊、包括不在生成樹的另一端點(diǎn)包括進(jìn)生成樹， …。 5.依次類推，直至將所有結(jié)點(diǎn)都包括進(jìn)生成樹為止

Pascal的渣渣代碼...

注：尋找最短的邊那一步可以用堆優(yōu)化，但那樣還不如直接用Kruskal......

Reference:　　http://www.nocow.cn/index.php/Prim%E7%AE%97%E6%B3%95

const vmax=1000; var w:array[1..vmax,1..vmax] of longint; i,j,k,v,e:longint; w:存儲鄰接矩陣 v:結(jié)點(diǎn)數(shù) e:邊數(shù)procedure prim(v0:longint); var flag:array[1..vmax] of boolean; //flag:表示是否在樹中。true是, false否min,prevk,nextk:longint; beginfillchar(flag,sizeof(flag),0);flag[v0]:=true; //STEP2for i:=1 to v-1 do //最小生成樹中有v-1條邊 ，所以外層循環(huán)需要v-1次 //STEP5beginmin:=maxlongint;for k:=1 to v do if flag[k] then //尋找在最小生成樹中的點(diǎn) k：當(dāng)前在最小生成樹中的點(diǎn)for j:=1 to v do //STEP3//尋找與（最小生成樹中的點(diǎn)）的距離最短的點(diǎn)。// j：當(dāng)前要找的不在最小生成樹中的點(diǎn) if (not flag[j]) and (w[k,j]<min) and (w[k,j]<>0) then紫色代碼：//判重：要找的點(diǎn)不能在最小生成樹中紅色代碼：//k與j必須相連！beginmin:=w[k,j];nextk:=j; prevk:=k; //這條邊從在最小生成樹中的點(diǎn)出發(fā) ，//擴(kuò)展到當(dāng)前不在最小生成樹中的點(diǎn)。//prevk:=k，prevk為起點(diǎn)，在最小生成樹中//nextk:=j，nextk為 終點(diǎn)，當(dāng)前不在最小生成樹中end;if min<>maxlongint then //如果找到了nextk這樣的可以從當(dāng)前最小生成樹中擴(kuò)展出來//（可以進(jìn)入最小生成樹）的點(diǎn)beginflag[nextk]:=true; //將nextk這樣的點(diǎn)加入最小生成樹 //STEP4writeln(prevk,‘ ’,nextk,‘ ’,min); //輸出這條邊end;end; end;begin fillchar(w,sizeof(w),0); readln(v,e); for k:=1 to e dobeginread(i,j);readln(w[i,j]);w[j,i]:=w[i,j];end;prim(1); //STEP1end. View Code

?

?

Kruskal：

算法步驟：

1、把圖中的邊按權(quán)值從小到大排序。 2、按從小到大的順序依次向樹中加邊。?????? 在添加每一條邊（u，v）時，如果u和V兩個點(diǎn)都已在樹中，一旦添加，就回構(gòu)成回路，所以放棄該邊，在向后找下一條邊。 3、直到添加n-1條邊。

用并查集優(yōu)化

#include <iostream> using namespace std;struct abc {int x,y,dat; };struct abc e[1000]; int f[1000]; int i,j,k,ans,n,m,tx,ty,tmp;int find(int x) {if (x!=f[x])f[x]=find(f[x]);return f[x]; }void iunion(int x,int y) {int fx=find(x);int fy=find(y);if (fx!=fy)f[fy]=fx; }void qsort(int l,int r) {int i,j,mid;struct abc t; i=l;j=r;mid=e[(l+r)/2].dat;do{while (e[i].dat<mid) i++;while (e[j].dat>mid) j--;if (!(i>j)){t=e[i];e[i]=e[j];e[j]=t;i++;j--;}}while (i<=j);if (l<j) qsort(l,j);if (i<r) qsort(i,r); }int main() {cin>>n>>m;for (i=1;i<=m;i++){cin>>tx>>ty>>tmp;e[i].x=tx;e[i].y=ty;e[i].dat=tmp;}for (i=1;i<=n;i++)f[i]=i;qsort(1,m);k=1;ans=0;for (i=1;i<=n-1;i++){while (find(e[k].x)==find(e[k].y)) k++;iunion(e[k].x,e[k].y);ans=ans+e[k].dat;cout<<e[k].x<<" "<<e[k].y<<" "<<e[k].dat<<endl;}cout<<ans<<endl; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/pdev/p/3869977.html

新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的Prim和Kruskal求最小生成树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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