1、實(shí) 驗(yàn) 報(bào) 告實(shí)驗(yàn)原理：Kruskal 算法是一種按照?qǐng)D中邊的權(quán)值遞增的順序構(gòu)造最小生成樹的方法。其基本思想是：設(shè)無向連通網(wǎng)為G（V，E），令G 的最小生成樹為T，其初態(tài)為T（V，），即開始時(shí)，最小生成樹T 由圖G 中的n 個(gè)頂點(diǎn)構(gòu)成，頂點(diǎn)之間沒有一條邊，這樣T 中各頂點(diǎn)各自構(gòu)成一個(gè)連通分量。然后，按照邊的權(quán)值由小到大的順序，考察G 的邊集E 中的各條邊。若被考察的邊的兩個(gè)頂點(diǎn)屬于T 的兩個(gè)不同的連通分量，則將此邊作為最小生成樹的邊加入到T 中，同時(shí)把兩個(gè)連通分量連接為一個(gè)連通分量；若被考察邊的兩個(gè)頂點(diǎn)屬于同一個(gè)連通分量，則舍去此邊，以免造成回路，如此下去，當(dāng)T 中的連通分量個(gè)數(shù)為1 時(shí)，此連

2、通分量便為G 的一棵最小生成樹。如教材153頁的圖4.21(a)所示，按照Kruskal 方法構(gòu)造最小生成樹的過程如圖4.21 所示。在構(gòu)造過程中，按照網(wǎng)中邊的權(quán)值由小到大的順序，不斷選取當(dāng)前未被選取的邊集中權(quán)值最小的邊。依據(jù)生成樹的概念，n 個(gè)結(jié)點(diǎn)的生成樹，有n1 條邊，故反復(fù)上述過程，直到選取了n1 條邊為止，就構(gòu)成了一棵最小生成樹。實(shí)驗(yàn)?zāi)康模罕緦?shí)驗(yàn)通過實(shí)現(xiàn)最小生成樹的算法，使學(xué)生理解圖的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)表示，并能理解最小生成樹Kruskal 算法。通過練習(xí)，加強(qiáng)對(duì)算法的理解，提高編程能力。實(shí)驗(yàn)內(nèi)容：（1）假定每對(duì)頂點(diǎn)表示圖的一條邊，每條邊對(duì)應(yīng)一個(gè)權(quán)值；（2）輸入每條邊的頂點(diǎn)和權(quán)值；（3）輸入

3、每條邊后，計(jì)算出最小生成樹；（4）打印最小生成樹邊的頂點(diǎn)及權(quán)值。實(shí)驗(yàn)器材（設(shè)備、元器件）：PC機(jī)一臺(tái)，裝有C語言集成開發(fā)環(huán)境。數(shù)據(jù)結(jié)構(gòu)與程序：#include #include #include using namespace std;#define X 105typedef struct Edgeint w;int x, y; Edge;/儲(chǔ)存邊的struct，并儲(chǔ)存邊兩端的結(jié)點(diǎn)class GraphNodepublic:int data;int father;int child; GraphNodeX;/儲(chǔ)存點(diǎn)信息的并查集類（點(diǎn)的值，父結(jié)點(diǎn)，子結(jié)點(diǎn)）Edge edgeX*X;bool co

4、mp(const Edge, const Edge);void update(int);int main()int node_num;int sum_weight = 0;FILE *in = fopen(C:Users瑞奇Desktop編程實(shí)驗(yàn)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)FileTempin.txt, r);cout Reading data from file. endl endl;/cout node_num;fscanf(in, %d, &node_num);/cout Please input the data of each node: endl;for(int i = 1;i GraphNode

5、i.data;fscanf(in, %d, &GraphNodei.data);GraphNodei.father = GraphNodei.child = i;/初始化點(diǎn)集/cout Please input the relation between nodes in this format and end with (0 0 0): endl (first_node second_node egde_weight) x y w & w)while(fscanf(in, %d%d%d, &x, &y, &w) != EOF & w)edgetmp_cnt.w = w, edgetmp_cnt

6、.x = x, edgetmp_cnt+.y = y;fclose(in);sort(edge+1, edge+tmp_cnt, comp);/對(duì)邊權(quán)進(jìn)行排序cout The MinSpanTree contains following edges: endl endl;for(int i = 1;i = tmp_cnt;i+)/循環(huán)找最小邊if(GraphNodeedgei.x.father != GraphNodeedgei.y.father)int n = edgei.x;int m = n;if(GraphNodem.father != m)/使用并查集對(duì)邊是否可用進(jìn)行判斷m = Gr

7、aphNodem.father;GraphNodem.father = GraphNodeedgei.y.father;GraphNodeedgei.x.father = GraphNodeedgei.y.father;GraphNodeedgei.y.child = GraphNodeedgei.x.child;while(GraphNoden.child != n)n = GraphNoden.child;update(n);/在合并點(diǎn)集后對(duì)并查集進(jìn)行更新sum_weight += edgei.w;/計(jì)算總權(quán)cout t The edge between GraphNodeedgei.x.

8、data & GraphNodeedgei.y.data with the weight edgei.w endl;cout endl And the total weight of the MinSpanTree add up to: sum_weight endl;return 0;bool comp(const Edge a, const Edge b)return a.w b.w;void update(int n)if(GraphNoden.father = n)return;GraphNodeGraphNoden.father.child = GraphNoden.child;/更

9、新孩子結(jié)點(diǎn)update(GraphNoden.father);/遞歸更新GraphNoden.father = GraphNodeGraphNoden.father.father;/更新父結(jié)點(diǎn)程序運(yùn)行結(jié)果：運(yùn)行程序，程序讀取文件，獲取文件中關(guān)于圖的信息：結(jié)點(diǎn)數(shù)，結(jié)點(diǎn)值，結(jié)點(diǎn)間邊權(quán)。然后使用Kruskal算法對(duì)錄入信息進(jìn)行處理：1. 對(duì)邊權(quán)排序2. 取最小權(quán)邊，若邊的端結(jié)點(diǎn)不在同一集合眾，則使邊的端結(jié)點(diǎn)加入集合并刪除該邊；若邊的端結(jié)點(diǎn)本來就在同一集合中，直接刪除該邊3. 循環(huán)執(zhí)行步驟2，直到集合中包含所有結(jié)點(diǎn)和結(jié)點(diǎn)數(shù)-1條邊輸入為：61 2 3 4 5 61 2 61 3 11 4 52 3 52 5 33 4 53 5 63 6 44 6 25 6 6程序運(yùn)行結(jié)果如下圖：實(shí)驗(yàn)結(jié)論：Kruskal算法其實(shí)是一種貪心