C語言實現最小生成樹構造算法

2020-01-26 13:33:42

字體：大中小

來源：轉載

供稿：網友

最小生成樹

最小生成樹（minimum spanning tree）是由n個頂點，n-1條邊，將一個連通圖連接起來，且使權值最小的結構。
最小生成樹可以用Prim（普里姆）算法或kruskal（克魯斯卡爾）算法求出。

我們將以下面的帶權連通圖為例講解這兩種算法的實現：

注：由于測試輸入數據較多，程序可以采用文件輸入

Prim（普里姆）算法

時間復雜度：O（N^2）（N為頂點數）
prim算法又稱“加點法”，用于邊數較多的帶權無向連通圖
方法：每次找與之連線權值最小的頂點，將該點加入最小生成樹集合中
注意：相同權值任選其中一個即可，但是不允許出現閉合回路的情況。

代碼部分通過以下步驟可以得到最小生成樹：

1.初始化：

lowcost[i]:表示以i為終點的邊的最小權值,當lowcost[i]=0表示i點加入了MST。
mst[i]:表示對應lowcost[i]的起點，當mst[i]=0表示起點i加入MST。
由于我們規定最開始的頂點是1，所以lowcost[1]=0，MST[1]=0。即只需要對2~n進行初始化即可。

#define MAX 100 #define MAXCOST 0x7fffffff int graph[MAX][MAX]; void prim(int graph[][MAX], int n) {  int lowcost[MAX];  int mst[MAX];  int i, j, min, minid, sum = 0;  for (i = 2; i <= n; i++)  {  lowcost[i] = graph[1][i];//lowcost存放頂點1可達點的路徑長度  mst[i] = 1;//初始化以1位起始點  }  mst[1] = 0;

2.查找最小權值及路徑更新

定義一個最小權值min和一個最小頂點ID minid，通過循環查找出min和minid，另外由于規定了某一頂點如果被連入，則lowcost[i]=0，所以不需要擔心重復點問題。所以找出的終點minid在MST[i]中可以找到對應起點，min為權值，直接輸出即可。
我們連入了一個新的頂點，自然需要對這一點可達的路徑及權值進行更新，所以循環中還應該包括路徑更新的代碼。

for (i = 2; i <= n; i++)  {  min = MAXCOST;  minid = 0;  for (j = 2; j <= n; j++)  {  if (lowcost[j] < min && lowcost[j] != 0)  {  min = lowcost[j];//找出權值最短的路徑長度  minid = j; //找出最小的ID  }  }  printf("V%d-V%d=%d/n",mst[minid],minid,min);  sum += min;//求和  lowcost[minid] = 0;//該處最短路徑置為0  for (j = 2; j <= n; j++) {  if (graph[minid][j] < lowcost[j])//對這一點直達的頂點進行路徑更新  {  lowcost[j] = graph[minid][j];  mst[j] = minid; }  }  }  printf("最小權值之和=%d/n",sum);}

具體代碼如下：

#include<stdio.h> #define MAX 100 #define MAXCOST 0x7fffffff int graph[MAX][MAX]; void prim(int graph[][MAX], int n) {  int lowcost[MAX];  int mst[MAX];  int i, j, min, minid, sum = 0;  for (i = 2; i <= n; i++)  {  lowcost[i] = graph[1][i];//lowcost存放頂點1可達點的路徑長度  mst[i] = 1;//初始化以1位起始點  }  mst[1] = 0;  for (i = 2; i <= n; i++)  {  min = MAXCOST;  minid = 0;  for (j = 2; j <= n; j++)  {  if (lowcost[j] < min && lowcost[j] != 0)  {  min = lowcost[j];//找出權值最短的路徑長度  minid = j; //找出最小的ID  }  }  printf("V%d-V%d=%d/n",mst[minid],minid,min);  sum += min;//求和  lowcost[minid] = 0;//該處最短路徑置為0  for (j = 2; j <= n; j++) {  if (graph[minid][j] < lowcost[j])//對這一點直達的頂點進行路徑更新  {  lowcost[j] = graph[minid][j];  mst[j] = minid; }  }  }  printf("最小權值之和=%d/n",sum);} int main() {  int i, j, k, m, n;  int x, y, cost;  //freopen("1.txt","r",stdin);//文件輸入  scanf("%d%d",&m,&n);//m=頂點的個數，n=邊的個數  for (i = 1; i <= m; i++)//初始化圖  {  for (j = 1; j <= m; j++)  {  graph[i][j] = MAXCOST;  }  }  for (k = 1; k <= n; k++)  {  scanf("%d%d%d",&i,&j,&cost); graph[i][j] = cost;  graph[j][i] = cost;  }  prim(graph, m);  return 0; }

編譯運行結果：

普里姆結果

kruskal（克魯斯卡爾）算法

時間復雜度：O（NlogN）（N為邊數）
kruskal算法又稱“加邊法”，用于邊數較少的稀疏圖
方法：每次找圖中權值最小的邊，將邊連接的兩個頂點加入最小生成樹集合中
注意：相同權值任選其中一個即可，但是不允許出現閉合回路的情況。

代碼部分通過以下步驟可以得到最小生成樹：

1.初始化：

構建邊的結構體，包括起始頂點、終止頂點，邊的權值
借用一個輔助數組vset[i]用來判斷某邊是否加入了最小生成樹集合

#define MAXE 100#define MAXV 100typedef struct{ int vex1; //邊的起始頂點 int vex2; //邊的終止頂點 int weight; //邊的權值}Edge;void kruskal(Edge E[],int n,int e){  int i,j,m1,m2,sn1,sn2,k,sum=0; int vset[n+1]; for(i=1;i<=n;i++) //初始化輔助數組 vset[i]=i; k=1;//表示當前構造最小生成樹的第k條邊，初值為1 j=0;//E中邊的下標，初值為0

2.取邊和輔助集合更新

按照排好的順序依次取邊，若不屬于同一集合則將其加入最小生成樹集合，每當加入新的邊，所連接的兩個點即納入最小生成樹集合，為避免重復添加，需要進行輔助集合更新
注：由于kruskal算法需要按照權值大小順序取邊，所以應該事先對圖按權值升序，這里我采用了快速排序算法，具體算法可以參照快速排序（C語言）

 while(k<e)//生成的邊數小于e時繼續循環 { m1=E[j].vex1; m2=E[j].vex2;//取一條邊的兩個鄰接點 sn1=vset[m1]; sn2=vset[m2];  //分別得到兩個頂點所屬的集合編號 if(sn1!=sn2)//兩頂點分屬于不同的集合，該邊是最小生成樹的一條邊 {//防止出現閉合回路  printf("V%d-V%d=%d/n",m1,m2,E[j].weight); sum+=E[j].weight; k++; //生成邊數增加 if(k>=n) break; for(i=1;i<=n;i++) //兩個集合統一編號 if (vset[i]==sn2) //集合編號為sn2的改為sn1 vset[i]=sn1; } j++; //掃描下一條邊 } printf("最小權值之和=%d/n",sum);}

具體算法實現：

#include <stdio.h>#define MAXE 100#define MAXV 100typedef struct{ int vex1; //邊的起始頂點 int vex2; //邊的終止頂點 int weight; //邊的權值}Edge;void kruskal(Edge E[],int n,int e){  int i,j,m1,m2,sn1,sn2,k,sum=0; int vset[n+1]; for(i=1;i<=n;i++) //初始化輔助數組 vset[i]=i; k=1;//表示當前構造最小生成樹的第k條邊，初值為1 j=0;//E中邊的下標，初值為0 while(k<e)//生成的邊數小于e時繼續循環 { m1=E[j].vex1; m2=E[j].vex2;//取一條邊的兩個鄰接點 sn1=vset[m1]; sn2=vset[m2];  //分別得到兩個頂點所屬的集合編號 if(sn1!=sn2)//兩頂點分屬于不同的集合，該邊是最小生成樹的一條邊 {//防止出現閉合回路  printf("V%d-V%d=%d/n",m1,m2,E[j].weight); sum+=E[j].weight; k++; //生成邊數增加  if(k>=n) break; for(i=1;i<=n;i++) //兩個集合統一編號 if (vset[i]==sn2) //集合編號為sn2的改為sn1 vset[i]=sn1; } j++; //掃描下一條邊 } printf("最小權值之和=%d/n",sum);}int fun(Edge arr[],int low,int high) { int key; Edge lowx; lowx=arr[low]; key=arr[low].weight; while(low<high) { while(low<high && arr[high].weight>=key) high--; if(low<high) arr[low++]=arr[high]; while(low<high && arr[low].weight<=key) low++; if(low<high) arr[high--]=arr[low]; } arr[low]=lowx; return low; } void quick_sort(Edge arr[],int start,int end){ int pos; if(start<end) { pos=fun(arr,start,end); quick_sort(arr,start,pos-1); quick_sort(arr,pos+1,end); }}int main(){ Edge E[MAXE]; int nume,numn; //freopen("1.txt","r",stdin);//文件輸入 printf("輸入頂數和邊數:/n"); scanf("%d%d",&numn,&nume); for(int i=0;i<nume;i++) scanf("%d%d%d",&E[i].vex1,&E[i].vex2,&E[i].weight); quick_sort(E,0,nume-1); kruskal(E,numn,nume);}

編譯運行結果：