克魯斯卡爾算法實驗報告

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

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

3、每條邊后，計算出最小生成樹；（4）打印最小生成樹邊的頂點及權值。實驗器材（設備、元器件）：PC機一臺，裝有C語言集成開發(fā)環(huán)境。數(shù)據(jù)結構與程序：#include #include #include using namespace std;#define X 105typedef struct Edgeint w;int x, y; Edge;/儲存邊的struct，并儲存邊兩端的結點class GraphNodepublic:int data;int father;int child; GraphNodeX;/儲存點信息的并查集類（點的值，父結點，子結點）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ù)據(jù)結構實驗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;/初始化點集/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);/對邊權進行排序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)/使用并查集對邊是否可用進行判斷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);/在合并點集后對并查集進行更新sum_weight += edgei.w;/計算總權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、新孩子結點update(GraphNoden.father);/遞歸更新GraphNoden.father = GraphNodeGraphNoden.father.father;/更新父結點程序運行結果：運行程序，程序讀取文件，獲取文件中關于圖的信息：結點數(shù)，結點值，結點間邊權。然后使用Kruskal算法對錄入信息進行處理：1. 對邊權排序2. 取最小權邊，若邊的端結點不在同一集合眾，則使邊的端結點加入集合并刪除該邊；若邊的端結點本來就在同一集合中，直接刪除該邊3. 循環(huán)執(zhí)行步驟2，直到集合中包含所有結點和結點數(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程序運行結果如下圖：實驗結論：Kruskal算法其實是一種貪心