最小生成樹之 prim算法和kruskal算法(以 hdu 1863為例)，kruskalhdu

最小生成樹之 prim算法和kruskal算法(以 hdu 1863為例)，kruskalhdu

最小生成樹的性質

MST性質：設G = (V,E)是連通帶權圖，U是V的真子集。如果(u,v)∈E,且u∈U,v∈V-U,且在所有這樣的邊中，

(u,v)的權c[u][v]最小，那麼一定存在G的一棵最小生成樹，(u,v)為其中一條邊。

構造最小生成樹，要解決以下兩個問題：
(1).盡可能選取權值小的邊，但不能構成回路（也就是環）。
(2).選取n-1條恰當的邊以連接網的n個頂點。

Prim算法的思想：

設G = (V,E)是連通帶權圖，V = {1,2,…,n}。先任選一點（一般選第一個點），首先置S = {1}，然後，只要S是V的真子集，就選取滿足條件i ∈S,j ∈V-S,且c[i][j]最小的邊，將頂點j添加到S中。這個過程一直進行到S = V時為止。在這個過程中選取到的所有邊恰好構成G的一棵最小生成樹。

 

Prim算法代碼     

以 hdu 1863為例 （點擊打開鏈接）

#include<stdio.h> #include<limits.h> #include<string.h> #define N 100 int n,m,map[N+5][N+5],v[N+5],low[N+5]; int prim() { int i,j,pos,min,s=0; memset(v,0,sizeof(v)); //v[i]用來標記i是否已訪問，先初始化為0，表示都未訪問 v[1]=1; //先任選一點作為第一個點 pos=1; //pos用來標記當前選的點的下標 for(i=2;i<=n;i++) low[i]=map[1][i]; //用low數組存已選點到其他點的權值 for(i=1;i<n;i++){ min=INT_MAX; for(j=1;j<=n;j++) //求權值最小的邊 if(!v[j]&&low[j]<min){ min=low[j]; pos=j; } if(min==INT_MAX) break; s+=min; v[pos]=1; for(j=1;j<=n;j++) //更新low數組 if(!v[j]&&map[pos][j]<low[j]) low[j]=map[pos][j]; } if(i!=n) s=-1; return s; } int main() { int i,j,s,a,b,c; while(scanf("%d%d",&m,&n)!=EOF){ //m為道路數，n為村莊數 if(m==0) break; for(i=1;i<=n;i++) for(j=1;j<=n;j++) map[i][j]=INT_MAX; //先將map數組初始化為很大的值（int 最大值） for(i=1;i<=m;i++){ scanf("%d%d%d",&a,&b,&c); map[a][b]=map[b][a]=c; //map[a][b]存的從a到b的權值 } s=prim(); if(s==-1) printf("?\n"); else printf("%d\n",s); } return 0; } View Code

 

Kruskal算法思想

給定無向連同帶權圖G = (V,E),V = {1,2,...,n}。

（1）首先將G的n個頂點看成n個孤立的連通分支。將所有的邊按權從小大排序。

（2）從第一條邊開始，依邊權遞增的順序檢查每一條邊。並按照下述方法連接兩個不同的連通分支：當查看到第k條邊(v,w)時，如果端點v和w分別是當前兩個不同的連通分支T1和T2的端點是，就用邊(v,w)將T1和T2連接成一個連通分支，然後繼續查看第k+1條邊；如果端點v和w在當前的同一個連通分支中，就直接再查看k+1條邊。這個過程一個進行到只剩下一個連通分支時為止。此時，已構成G的一棵最小生成樹。

Kruskal算法代碼：

以 hdu 1863為例 （點擊打開鏈接）

1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 int f[105],n,m; 5 struct stu 6 { 7 int a,b,c; 8 }t[5500]; 9 int cmp(struct stu x,struct stu y) 10 { 11 return x.c<y.c; 12 } 13 int find(int x) //路徑壓縮，找父節點 14 { 15 if(x!=f[x]) 16 f[x]=find(f[x]); 17 return f[x]; 18 } 19 int krus() 20 { 21 int i,k=0,s=0,x,y; 22 for(i=1;i<=n;i++){ 23 x=find(t[i].a); 24 y=find(t[i].b); 25 if(x!=y){ //最小生成樹不能形成環，所以要判斷它們的是否屬於同一集合 26 s+=t[i].c; 27 k++; 28 if(k==m-1) //<span>29 break; 30 f[x]=y; //將父節點更新 31 } 32 } 33 if(k!=m-1) 34 s=-1; 35 return s; 36 } 37 int main() 38 { 39 int i,s; 40 while(scanf("%d%d",&n,&m)!=EOF){ 41 if(n==0) 42 break; 43 for(i=1;i<=n;i++) 44 scanf("%d%d%d",&t[i].a,&t[i].b,&t[i].c); 45 for(i=1;i<=m;i++) //f[i]存的結點i的父親，先將其父親都初始化為其本身 46 f[i]=i; 47 sort(t+1,t+1+n,cmp); //按權值從小到大排序 48 s=krus(); 49 if(s==-1) 50 printf("?\n"); 51 else 52 printf("%d\n",s); 53 } 54 return 0; 55 } View Code

 

 

注：若頂點數為n,邊為e

prim算法適合稠密圖，其時間復雜度為O(n^2)，其時間復雜度與邊的數目無關，

而kruskal算法的時間復雜度為O(eloge)跟邊的數目有關，適合稀疏圖。

用prim算法與Kruskal算法最小生成樹，跪不要原代碼要過程

V: {1,2,3,4,5,6,7}E: {a:(1,2):50, b:(1,3):60, c:(2,4):65, d:(2,5):40, e:(3,4):52, f:(3,7):45, g:(4,5):50, h:(4,6):30, i:(4,7):42, j:(5,6):70}kruskal
0: V={{1},{2},{3},{4},{5},{6},{7}}, E={}, pick 1st from {h,d,i,f,a,g,e,b,c,j}1: V={{1},{2},{3},{4,6},{5},{7}}, E={h}, pick 1st from {d,i,f,a,g,e,b,c,j}2: V={{1},{2,5},{3},{4,6},{7}}, E={h,d}, pick 1st from {i,f,a,g,e,b,c,j}3: V={{1},{2,5},{3},{4,6,7}}, E={h,d,i}, pick 1st from {f,a,g,e,b,c,j}4: V={{1},{2,5},{3,4,6,7}}, E={h,d,i,f}, pick 1st from {a,g,b,c,j}5: V={{1,2,5},{3,4,6,7}}, E={h,d,i,f,a}, pick 1st from {g,b,c,j}6: V={{1,2,5,3,4,6,7}}, E={h,d,i,f,a,g}, pick 1st from {}#: final V={1,2,5,3,4,6,7}, E={h,d,i,f,a,g}prim
Vstart = 10: V={1}, E={}, pick 1st from {a,b}1: V={1,2}, E={a}, pick 1st from {d,b,c}2: V={1,2,5}, E={a,d}, pick 1st from {g,b,c,j}3: V={1,2,5,4}, E={a,d,g}, pick 1st from {h,i,e,b}4: V={1,2,5,4,6}, E={a,d,g,h}, pick 1st from {i,e,b}5: V={1,2,5,4,6,7}, E={a,d,g,h,i}, pick 1st from {e,b}6: V={1,2,5,4,6,7,3}, E={a,d,g,h,i,e}.
 

急數據結構最小生成樹prim算法C語言實現

Kruskal算法：
void Kruskal(Edge E[],int n,int e)
{
int i,j,m1,m2,sn1,sn2,k;
int vset[MAXE];
for (i=0;i<n;i++) vset[i]=i; //初始化輔助數組
k=1; //k表示當前構造最小生成樹的第幾條邊,初值為1
j=0; //E中邊的下標,初值為0
while (k<n) //生成的邊數小於n時循環
{
m1=E[j].u;m2=E[j].v; //取一條邊的頭尾頂點
sn1=vset[m1];sn2=vset[m2]; //分別得到兩個頂點所屬的集合編號
if (sn1!=sn2) //兩頂點屬於不同的集合,該邊是最小生成樹的一條邊
{
printf(" (%d,%d):%d/n",m1,m2,E[j].w);
k++; //生成邊數增1
for (i=0;i<n;i++) //兩個集合統一編號
if (vset[i]==sn2) //集合編號為sn2的改為sn1
vset[i]=sn1;
}
j++; //掃描下一條邊
}
}
Prim算法：
void prim(MGraph g,int v)
{
int lowcost[MAXV],min,n=g.vexnum;
int closest[MAXV],i,j,k;
for (i=0;i<n;i++) //給lowcost[]和closest[]置初值
{
lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for (i=1;i<n;i++) //找出n-1個頂點
{
min=INF;
for (j=0;j<n;j++) //在(V-U)中找出離U最近的頂點k
if (lowcost[j]!=0 && lowcost[j]<min)
{
min=lowcost[j];k=j;
}
printf(" 邊(%d,%d)權為:%d/n",closest[k],k,min);
lowcost[k]=0; //標記k已經加入U
for (j=0;j<n;j++) //修改數組lowcost和closest
if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j])
{
lowcost[j]=g.edges[k][j];closest[j]=k;
}
}
}...余下全文>>