最小生成樹之kruskal算法

　　1. Kruskal算法

　　(1) 算法思想

　　K r u s k a l算法每次選擇n- 1條邊，所使用的貪婪準則是：從剩下的邊中選擇一條不會產生環路的具有最小耗費的邊加入已選擇的邊的集合中。注意到所選取的邊若產生環路則不可能形成一棵生成樹。K r u s k a l算法分e 步，其中e 是網絡中邊的數目。按耗費遞增的順序來考慮這e 條邊，每次考慮一條邊。當考慮某條邊時，若將其加入到已選邊的集合中會出現環路，則將其拋棄，否則，將它選入。

　　初始時沒有任何邊被選擇。邊( 1 , 6)是最先選入的邊，它被加入到欲構建的生成樹中，得到圖1 3 - 1 2 c。下一步選擇邊( 3，4)并將其加入樹中(如圖1 3 - 1 2 d所示)。然后考慮邊( 2，7 ，將它加入樹中并不會產生環路，于是便得到圖1 3 - 1 2 e。下一步考慮邊( 2，3)并將其加入樹中(如圖1 3 - 1 2 f所示)。在其余還未考慮的邊中，(7，4)具有最小耗費，因此先考慮它，將它加入正在創建的樹中會產生環路，所以將其丟棄。此后將邊( 5，4)加入樹中，得到的樹如圖13-12g 所示。下一步考慮邊( 7，5)，由于會產生環路，將其丟棄。最后考慮邊( 6，5)并將其加入樹中，產生了一棵生成樹，其耗費為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語言常見知識點總結