數(shù)據(jù)結(jié)構(gòu)課程設(shè)計論文-用Kruskal算法求解其所有的最小生成樹

1、精品文檔合肥學(xué)院計算機科學(xué)與技術(shù)系課程設(shè)計報告20212021 學(xué)年第 2 學(xué)期課程 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計題目名稱用Kruskal算法求解其所有的最小生成樹學(xué)生姓名童子軒學(xué)號1204013037專業(yè)班級12級計本3班指導(dǎo)教師何立新2021 年 9 月題目 設(shè)計程序完成如下功能：對給定的網(wǎng)和起點，用Kruskal算法的根本思想求解其所有的最小生成樹。1、 問題分析及問題定義 題目中的要求是用Kruskal算法來求解最小生成樹，首先要弄清楚最小生成樹是什么，怎么生成最小生成樹以及Kruskal算法的根本思想。 最小生成樹的定義是：在圖論中，常常將樹定義為一個無回路連通圖。對于一個帶權(quán)的無向連通圖

2、，其每個生成樹所有邊上的權(quán)值之和可能不同，我們把所有邊上權(quán)值之和最小的生成樹稱為圖的最小生成樹。在一給定的無向圖G = (V, E)中，(u, v)代表連接頂點u與頂點v的邊，而 w(u,v) 代表此邊的權(quán)重，假設(shè)存在T為 E 的子集且為無循環(huán)圖，使得權(quán)重之和w(T) 最小，那么此T為G的最小生成樹。 最小生成樹的特性有：任意一棵樹的最小生成樹邊上的權(quán)值之和最小，最小生成樹可能不唯一，因為它們的權(quán)值之和相等。大多數(shù)解決該類問題的算法都基于最小生成樹的MST性質(zhì)。在一個連通網(wǎng)N=V,E中，U是頂點集V的一個非空子集。如果存在一條具有最小權(quán)值的邊(u,v)，其中uU,v(U-V),那么必存在一棵包

3、含(u,v)的最小生成樹。 克魯斯卡爾算法的根本思想是：假設(shè) WN=(V,E) 是一個含有 n 個頂點的連通網(wǎng)，那么按照克魯斯卡爾算法構(gòu)造最小生成樹的過程為：先構(gòu)造一個只含 n 個頂點，而邊集為空的子圖，假設(shè)將該子圖中各個頂點看成是各棵樹上的根結(jié)點，那么它是一個含有 n 棵樹的一個森林。之后，從網(wǎng)的邊集 E 中選取一條權(quán)值最小的邊，假設(shè)該條邊的兩個頂點分屬不同的樹，那么將其參加子圖，也就是說，將這兩個頂點分別所在的兩棵樹合成一棵樹；反之，假設(shè)該條邊的兩個頂點已落在同一棵樹上，那么不可取，而應(yīng)該取下一條權(quán)值最小的邊再試之。依次類推，直至森林中只有一棵樹，也即子圖中含有 n-1條邊為止。 假設(shè)有一

4、張圖，有假設(shè)干個點和邊，使用克魯斯卡爾算法生成最小生成樹的根本步驟是： 1首先將所有的邊的長度進行排序，用排序結(jié)果作為后面選擇邊的依據(jù)。選擇長度最小的一條邊，如果存在多條長度一樣小的邊，任選一條。 2如果有長度一樣小的邊，再選擇這樣的另外幾條邊。 3按照邊的長度遞增的順序來選擇邊，如果構(gòu)成環(huán)路那么將這條邊舍棄，選擇其他邊，當所有點都連通了后，最小生成樹就構(gòu)建完成。 所以解決問題的方案是首先選擇一種方式來存儲圖中各點與邊的信息，然后用冒泡排序?qū)λ羞叺臋?quán)值進行排序，再用克魯斯卡爾算法求網(wǎng)的最小生成樹，最后按父親結(jié)點和子女結(jié)點集的形式輸出生成樹中各條邊以及它們的權(quán)值。2、 數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計

5、 題目要求是生成最小生成樹，要對圖中各邊的權(quán)值進行比擬和選擇，所以采用鄰接矩陣來存儲。 存儲圖中各點的結(jié)構(gòu)體，bv表示起點，tv表示終點，w表示權(quán)值sstruct edgesint bv; int tv; int w; ; 概要設(shè)計：1對圖中各權(quán)值進行排序 排序是通過子函數(shù)void insertsort(edgeset ge,int e)來實現(xiàn)的，這里面權(quán)值的指代方式不同，在建立無向圖的時候是通過邊的兩個頂點來存儲權(quán)值，但是在權(quán)值排序的時候只需要用圖中邊的數(shù)組來比擬各權(quán)值的大小。利用二重for循環(huán)，假設(shè)一條邊的權(quán)值比另一條邊的權(quán)值大，然后利用數(shù)組ge0把兩條邊的起始點、結(jié)束點以及權(quán)值進行交換，

6、然后再按照換過之后的順序從小到大把權(quán)值輸出。2利用子函數(shù)int seeks(int set,int v)來判斷最長小生成樹是否構(gòu)成回路。按照權(quán)值排序的結(jié)果從最小權(quán)值的邊開始比擬。假設(shè)最小生成樹的第一條邊和第二條邊已選定，那么判斷是否構(gòu)成回路就從三條邊的起點和終點判斷，如果兩兩相同的話那就構(gòu)成回路了。3克魯斯卡爾算法構(gòu)造最小生成樹 克魯斯卡爾的算法思想是假設(shè)連通網(wǎng)N=V，E，那么令最小生成樹的起始狀態(tài)為只有n個頂點而無邊的非連通圖T=V，圖中每個頂點自成一個連通分量。在E中選擇代價最小的邊，假設(shè)該邊依附的頂點落在T中不同的連通分量上，那么將此邊加到T中，否那么舍去此邊而選擇下一條代價最小的邊。以

7、此類推，直至T中所有的頂點都在同一連通分量上為止。3、 詳細設(shè)計及編碼1克魯斯卡爾算法的實現(xiàn)void kruskal(edgeset ge,int n,int e) int setMAXE,v1,v2,i,j;int x;int y=1; edgeset xyMAXE;for(i=1;i<n+1;i+) seti=0; i=1; j=1; printf("第%d個最小生成樹:n",1);while(j<=e&&i<=n-1) v1=seeks(set,gej.bv); v2=seeks(set,gej.tv); if(v1!=v2) xyj

8、=gej;printf("(%d,%d):%dn",gej.bv,gej.tv,gej.w); setv1=v2; i+; /計數(shù)器判斷頂點數(shù)是否溢出 j+; y+;while(gej-1.w=gej.w)printf("第%d個最小生成樹為:n",y);for(x=1;x<=j-2;x+)printf("(%d,%d):%dn",xyx.bv,xyx.tv,xyx.w);printf("(%d,%d):%dn",gej.bv,gej.tv,gej.w);j+;y+; 2各邊權(quán)值的排序void inserts

9、ort(edgeset ge,int e)/對權(quán)值進行排序 int i,j; for(i=2;i<=e;i+) if(gei.w<gei-1.w) ge0=gei; j=i-1; while(ge0.w<gej.w) gej+1=gej; j-; gej+1=ge0; （3） 判斷最小生成樹是否構(gòu)成回路int seeks(int set,int v) int i; i=v; while(seti>0)i=seti; return i; 4主函數(shù)main() edgeset geMAXE; int a,n,e,i; printf("請輸入頂點個數(shù):")

10、; scanf("%d",&n); printf("請輸入邊的條數(shù):"); scanf("%d",&e); printf("請輸入邊的信息起點，終點，權(quán)值:n"); for(i=1;i<=e;i+) scanf("%d,%d,%d",&gei.bv,&gei.tv,&gei.w); printf("在以下菜單中進行選擇：n"); printf("1.kruskal算法起點，終點權(quán)值：n"); printf(&q

11、uot;2.exit退出：n"); scanf("%d",&a); while(a!=2) switch(a) case 1:insertsort(ge,e); kruskal(ge,n,e); break; printf("在以下菜單中進行選擇：n"); printf("1.kruskal算法起點，終點權(quán)值：n"); printf("2.exit退出：n"); scanf("%d",&a); return 1; 4、 上機調(diào)試過程1語法錯誤：程序中使用到的變量較多，既

12、有循環(huán)控制又有圖的頂點信息和邊信息的變量和數(shù)組下標及頂點數(shù)和邊數(shù)。所以在編程中出現(xiàn)了屢次變量使用不當和未事先定義以及重復(fù)定義的錯誤，經(jīng)過編譯器編譯之后的提示進行了修改。另外程序中有很多關(guān)于結(jié)構(gòu)體的操作，常有該變量不包含于某個結(jié)構(gòu)體和操作非法的錯誤，通過編譯器的提示進行了更正。2邏輯漏洞：在對圖中權(quán)值進行排序的時候，最小的權(quán)值出現(xiàn)了0，然后會導(dǎo)致最小生成樹的結(jié)果出現(xiàn)兩點沒有連在一起的邊，后來發(fā)現(xiàn)代碼中開始講所有邊權(quán)值初始化為0。還有就是在程序完成后發(fā)現(xiàn)程序只能生成一個最小生成樹，當存在有兩個相同的權(quán)值的情況下，不能生成所有的最小生成樹。3功能實現(xiàn)不完善：最開始程序完成的時候，忽略了要生成所有最小

13、生成樹這個要求，在特殊情況下也只能生成一個最小生成樹。然后通過跟同學(xué)的討論，分析最小生成樹的最短邊都相同，最長邊有相同邊的時候才有多種情況，所以用循環(huán)語句while(gej-1.w=gej.w)來找相同邊存在的情況。4經(jīng)驗和體會：因為我們教材上提到克魯斯卡爾算法思想，因此，拿到這個題目，感到并不陌生，把課本的思想看過以后，大概有了一個框架，再根據(jù)題目要求明確了程序編寫的流程，知道先進行什么，后進行什么。題目要求對于給自己定義的網(wǎng)，用克魯斯卡爾算法求出所有的最小生成樹。首先，應(yīng)該根據(jù)課題的要求對題意進行分析，將所遇到的問題進行歸納和總結(jié)，在本設(shè)計中，題意要求對給定的網(wǎng)和起點，用克魯斯卡爾算法的根

14、本思想求解出所有的最小生成樹，我們應(yīng)該了解關(guān)于網(wǎng)的一些根本概念和生成樹與最小生成樹之間有何區(qū)別和聯(lián)系，主要是要明確的理解克魯斯卡爾算法的根本思想。其次，針對出現(xiàn)的問題查找相關(guān)資料將其解決，主要應(yīng)該查找有關(guān)克魯斯卡爾算法根本思想方面的詳細介紹，當所有的問題得到解決后，對本設(shè)計應(yīng)該有個整體的思路并通過編寫各個函數(shù)模塊去實現(xiàn)課題的功能；最后，將編寫的源程序代碼在計算機上調(diào)試運行，直至調(diào)試成功。五、測試結(jié)果及分析圖 5-1圖 5-26、 用戶使用說明 在本設(shè)計中，是通過給定任意網(wǎng)和起點求出最小生成樹。程序最大頂點數(shù)和邊數(shù)規(guī)定為20可以在程序中任意設(shè)定大小。當編譯、運行之后，屏幕會顯示如下信息，用戶可以

15、根據(jù)以下使用說明做相關(guān)操作：1、 請輸入邊數(shù)和頂點數(shù)。您可以輸入在定義范圍之內(nèi)的任意值。2 、根據(jù)提示請輸入邊的信息。包括起點、終點和權(quán)值。3 、輸入完成后會出來2個選項。1是用克魯斯卡爾算法計算最小生成樹，2是選擇退出。4 、 選擇1后，最小生成樹的結(jié)果就出來了。7、 參考文獻1.徐孝凱，數(shù)據(jù)結(jié)構(gòu)實用教程，清華大學(xué)出版社，2005年7月。2.赫阿朋，C+應(yīng)用編程，電子工業(yè)出版，2003年4月。3.譚浩強，C語言程序設(shè)計教程，高等教育出版社，2004年5月。4.王昆侖,李紅,數(shù)據(jù)結(jié)構(gòu)與算法(第二版)中國鐵道出版社,2021年9月5李廉治，姜文清，郭福順?數(shù)據(jù)結(jié)構(gòu)?，大連理工大學(xué)出版社，1989

16、年八、附錄#include"stdio.h" #define MAXE 100 struct edgesint bv; int tv; int w; ; typedef struct edges edgeset; int seeks(int set,int v) int i; i=v; while(seti>0)i=seti; return i; void kruskal(edgeset ge,int n,int e) int setMAXE,v1,v2,i,j;int x;int y=1; edgeset xyMAXE;for(i=1;i<n+1;i+) se

17、ti=0; i=1; j=1; printf("第%d個最小生成樹:n",1);while(j<=e&&i<=n-1) v1=seeks(set,gej.bv); v2=seeks(set,gej.tv); if(v1!=v2) xyj=gej;printf("(%d,%d):%dn",gej.bv,gej.tv,gej.w); setv1=v2; i+; /計數(shù)器判斷頂點數(shù)是否溢出 j+; y+;while(gej-1.w=gej.w)printf("第%d個最小生成樹為:n",y);for(x=1;x&

18、lt;=j-2;x+)printf("(%d,%d):%dn",xyx.bv,xyx.tv,xyx.w);printf("(%d,%d):%dn",gej.bv,gej.tv,gej.w);j+;y+; void insertsort(edgeset ge,int e)/對權(quán)值進行排序 int i,j; for(i=2;i<=e;i+) if(gei.w<gei-1.w) ge0=gei; j=i-1; while(ge0.w<gej.w) gej+1=gej; j-; gej+1=ge0; main() edgeset geMAXE; int a,n,e,i; pri