快捷導(dǎo)航

C語(yǔ)言實(shí)現(xiàn)最小生成樹(shù)構(gòu)造算法

更新時(shí)間：2019年01月17日 11:41:31 作者：n.xuanrui

這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)最小生成樹(shù)構(gòu)造算法，利用Prim算法或kruskal算法求解，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

最小生成樹(shù)

最小生成樹(shù)（minimum spanning tree）是由n個(gè)頂點(diǎn)，n-1條邊，將一個(gè)連通圖連接起來(lái)，且使權(quán)值最小的結(jié)構(gòu)。
最小生成樹(shù)可以用Prim（普里姆）算法或kruskal（克魯斯卡爾）算法求出。

我們將以下面的帶權(quán)連通圖為例講解這兩種算法的實(shí)現(xiàn)：

注：由于測(cè)試輸入數(shù)據(jù)較多，程序可以采用文件輸入

Prim（普里姆）算法

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

代碼部分通過(guò)以下步驟可以得到最小生成樹(shù)：

1.初始化：

lowcost[i]:表示以i為終點(diǎn)的邊的最小權(quán)值,當(dāng)lowcost[i]=0表示i點(diǎn)加入了MST。
mst[i]:表示對(duì)應(yīng)lowcost[i]的起點(diǎn)，當(dāng)mst[i]=0表示起點(diǎn)i加入MST。
由于我們規(guī)定最開(kāi)始的頂點(diǎn)是1，所以lowcost[1]=0，MST[1]=0。即只需要對(duì)2~n進(jì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存放頂點(diǎn)1可達(dá)點(diǎn)的路徑長(zhǎng)度 
 mst[i] = 1;//初始化以1位起始點(diǎn) 
 } 
 mst[1] = 0;

2.查找最小權(quán)值及路徑更新

定義一個(gè)最小權(quán)值min和一個(gè)最小頂點(diǎn)ID minid，通過(guò)循環(huán)查找出min和minid，另外由于規(guī)定了某一頂點(diǎn)如果被連入，則lowcost[i]=0，所以不需要擔(dān)心重復(fù)點(diǎn)問(wèn)題。所以找出的終點(diǎn)minid在MST[i]中可以找到對(duì)應(yīng)起點(diǎn)，min為權(quán)值，直接輸出即可。
我們連入了一個(gè)新的頂點(diǎn)，自然需要對(duì)這一點(diǎn)可達(dá)的路徑及權(quán)值進(jìn)行更新，所以循環(huán)中還應(yīng)該包括路徑更新的代碼。

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];//找出權(quán)值最短的路徑長(zhǎng)度 
 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])//對(duì)這一點(diǎn)直達(dá)的頂點(diǎn)進(jìn)行路徑更新 
 { 
 lowcost[j] = graph[minid][j]; 
 mst[j] = minid;
 } 
 } 
 } 
 printf("最小權(quán)值之和=%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存放頂點(diǎn)1可達(dá)點(diǎn)的路徑長(zhǎng)度 
 mst[i] = 1;//初始化以1位起始點(diǎn) 
 } 
 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];//找出權(quán)值最短的路徑長(zhǎng)度 
 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])//對(duì)這一點(diǎn)直達(dá)的頂點(diǎn)進(jìn)行路徑更新 
 { 
 lowcost[j] = graph[minid][j]; 
 mst[j] = minid;
 } 
 } 
 } 
 printf("最小權(quán)值之和=%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=頂點(diǎn)的個(gè)數(shù)，n=邊的個(gè)數(shù) 

 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; 
}

編譯運(yùn)行結(jié)果：

普里姆結(jié)果

kruskal（克魯斯卡爾）算法

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

代碼部分通過(guò)以下步驟可以得到最小生成樹(shù)：

1.初始化：

構(gòu)建邊的結(jié)構(gòu)體，包括起始頂點(diǎn)、終止頂點(diǎn)，邊的權(quán)值
借用一個(gè)輔助數(shù)組vset[i]用來(lái)判斷某邊是否加入了最小生成樹(shù)集合

#define MAXE 100
#define MAXV 100
typedef struct{
 int vex1; //邊的起始頂點(diǎn)
 int vex2; //邊的終止頂點(diǎn)
 int weight; //邊的權(quán)值
}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++) //初始化輔助數(shù)組
 vset[i]=i;
 k=1;//表示當(dāng)前構(gòu)造最小生成樹(shù)的第k條邊，初值為1
 j=0;//E中邊的下標(biāo)，初值為0

2.取邊和輔助集合更新

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

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

具體算法實(shí)現(xiàn)：

#include <stdio.h>
#define MAXE 100
#define MAXV 100
typedef struct{
 int vex1; //邊的起始頂點(diǎn)
 int vex2; //邊的終止頂點(diǎn)
 int weight; //邊的權(quán)值
}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++) //初始化輔助數(shù)組
 vset[i]=i;
 k=1;//表示當(dāng)前構(gòu)造最小生成樹(shù)的第k條邊，初值為1
 j=0;//E中邊的下標(biāo)，初值為0
 while(k<e)//生成的邊數(shù)小于e時(shí)繼續(xù)循環(huán)
 {
 m1=E[j].vex1;
 m2=E[j].vex2;//取一條邊的兩個(gè)鄰接點(diǎn)
 sn1=vset[m1];
 sn2=vset[m2]; 
 //分別得到兩個(gè)頂點(diǎn)所屬的集合編號(hào)
 if(sn1!=sn2)//兩頂點(diǎn)分屬于不同的集合，該邊是最小生成樹(shù)的一條邊
 {//防止出現(xiàn)閉合回路 
 printf("V%d-V%d=%d\n",m1,m2,E[j].weight);
 sum+=E[j].weight;
 k++; //生成邊數(shù)增加 
 if(k>=n)
 break;
 for(i=1;i<=n;i++) //兩個(gè)集合統(tǒng)一編號(hào)
 if (vset[i]==sn2) //集合編號(hào)為sn2的改為sn1
 vset[i]=sn1;
 }
 j++; //掃描下一條邊
 }
 printf("最小權(quán)值之和=%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("輸入頂數(shù)和邊數(shù):\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);
}

編譯運(yùn)行結(jié)果：