最小生成樹之kruskal算法
1. Kruskal算法
(1) 算法思想
K r u s k a l算法每次選擇n- 1條邊,所使用的貪婪準則是:從剩下的邊中選擇一條不會產(chǎn)生環(huán)路的具有最小耗費的邊加入已選擇的邊的集合中。注意到所選取的邊若產(chǎn)生環(huán)路則不可能形成一棵生成樹。K r u s k a l算法分e 步,其中e 是網(wǎng)絡中邊的數(shù)目。按耗費遞增的順序來考慮這e 條邊,每次考慮一條邊。當考慮某條邊時,若將其加入到已選邊的集合中會出現(xiàn)環(huán)路,則將其拋棄,否則,將它選入。
初始時沒有任何邊被選擇。邊( 1 , 6)是最先選入的邊,它被加入到欲構(gòu)建的生成樹中,得到圖1 3 - 1 2 c。下一步選擇邊( 3,4)并將其加入樹中(如圖1 3 - 1 2 d所示)。然后考慮邊( 2,7 ,將它加入樹中并不會產(chǎn)生環(huán)路,于是便得到圖1 3 - 1 2 e。下一步考慮邊( 2,3)并將其加入樹中(如圖1 3 - 1 2 f所示)。在其余還未考慮的邊中,(7,4)具有最小耗費,因此先考慮它,將它加入正在創(chuàng)建的樹中會產(chǎn)生環(huán)路,所以將其丟棄。此后將邊( 5,4)加入樹中,得到的樹如圖13-12g 所示。下一步考慮邊( 7,5),由于會產(chǎn)生環(huán)路,將其丟棄。最后考慮邊( 6,5)并將其加入樹中,產(chǎn)生了一棵生成樹,其耗費為9 9。圖1 - 1 3給出了K r u s k a l算法的偽代碼。
(2)C代碼
/* Kruskal.c
Copyright (c) 2002, 2006 by ctu_85
All Rights Reserved.
*/
/* I am sorry to say that the situation of unconnected graph is not concerned */
#include "stdio.h"
#define maxver 10
#define maxright 100
int G[maxver][maxver],record=0,touched[maxver][maxver];
int circle=0;
int FindCircle(int,int,int,int);
int main()
{
int path[maxver][2],used[maxver][maxver];
int i,j,k,t,min=maxright,exsit=0;
int v1,v2,num,temp,status=0;
restart:
printf("Please enter the number of vertex(s) in the graph:\n");
scanf("%d",&num);
if(num>maxver||num<0)
{
printf("Error!Please reinput!\n");
goto restart;
相關(guān)推薦:北京 | 天津 | 上海 | 江蘇 | 山東 |
安徽 | 浙江 | 江西 | 福建 | 深圳 |
廣東 | 河北 | 湖南 | 廣西 | 河南 |
海南 | 湖北 | 四川 | 重慶 | 云南 |
貴州 | 西藏 | 新疆 | 陜西 | 山西 |
寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
黑龍江 | 內(nèi)蒙古 |