2011年計算機等級考試二級C輔導實例編程(4)

　　最小生成樹之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)是最先選入的邊，它被加入到欲構建的生成樹中，得到圖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;

　　2011計算機等級二級C語言五套模擬試題及答案

　　計算機等級考試二級C語言歷年真題匯總(2005-2010)

　　2011年計算機等級考試二級C語言常見問題匯總

　　計算機等級考試二級C語言常見知識點總結