數(shù)據(jù)結(jié)構(gòu)論文最小生成樹(shù)

1、課題：最小生成樹(shù)問(wèn)題 任課老師：朱節(jié)中 專業(yè)：軟件工程年級(jí)：2012級(jí)班級(jí)：1班學(xué)號(hào)：20122344001姓名：董上琦目錄1. 設(shè)計(jì)題目2. 需求分析1）運(yùn)行環(huán)境2）輸入的形式和輸入值的范圍3）輸出的形式描述4）功能描述5）測(cè)試數(shù)據(jù)3. 概要設(shè)計(jì)1）抽象數(shù)據(jù)類型定義描述.2）功能模塊設(shè)計(jì)3）模塊層次調(diào)用關(guān)系圖4. 詳細(xì)設(shè)計(jì)。實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有的類的定義及類中成員函數(shù)，并對(duì)主要的模塊寫出偽碼算法5. 調(diào)試分析。包括調(diào)試過(guò)程中遇到的問(wèn)題及解決的方法、算法的時(shí)間空間復(fù)雜性分析、經(jīng)驗(yàn)體會(huì)6. 用戶使用說(shuō)明。詳細(xì)列出每一步的操作說(shuō)明7. 測(cè)試結(jié)果8. 附錄：程序設(shè)計(jì)源代碼、設(shè)計(jì)題目1）.問(wèn)題描述

2、在n個(gè)城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟(jì)的架設(shè)方法。存儲(chǔ) 結(jié)構(gòu)采用多種。求解算法多種。2）.基本要求以鄰接多重表存儲(chǔ)無(wú)向帶權(quán)圖，利用克魯斯卡爾算法或普瑞姆算法求網(wǎng)的最 小生成樹(shù)。、需求分析1）運(yùn)行環(huán)境軟件在JDK運(yùn)行，硬件支持windows系統(tǒng)2）輸入的形式和輸入值的范圍自動(dòng)生成頂點(diǎn)數(shù)據(jù)在1020之間；各個(gè)頂點(diǎn)之間權(quán)值在2550之間；通過(guò)程序 改動(dòng)亦可生成已知頂點(diǎn)權(quán)值之間的最小生成樹(shù)，需將隨機(jī)生成代碼改為edge edge=new edge（0,1,16）,new（0,2,18） ；將已知頂點(diǎn)、權(quán)值通過(guò)其函數(shù)輸入再生成其所對(duì)應(yīng)最小生成樹(shù)。3）輸出的形式描述輸出隨機(jī)生成頂點(diǎn)個(gè)數(shù)以及各個(gè)

3、頂點(diǎn)之間權(quán)值；然后輸出本次生成頂點(diǎn)之間構(gòu)成的最小生成樹(shù)。4）功能描述該程序會(huì)自動(dòng)生成介于1020個(gè)數(shù)頂點(diǎn)模擬各城市，再隨機(jī)生成介于2550之間數(shù)值作為權(quán)值模擬各個(gè)城市間的距離，并同時(shí)生成此次頂點(diǎn)、權(quán)值相對(duì)應(yīng)的最小生成樹(shù)，模擬各城市間的最小距離，最小生成樹(shù)。如有確定城市頂點(diǎn)及其權(quán) 值，則可改動(dòng)程序令其不再隨機(jī)生成頂點(diǎn)權(quán)值，在程序中輸入如下代碼：edge edge=new edge（0,1,16）,new（0,2,18） 輸入數(shù)組為edge數(shù)組，edge （起點(diǎn)，終點(diǎn)，權(quán)值）。通過(guò)將隨機(jī)生成代碼改 動(dòng)就可以生成該城市對(duì)應(yīng)權(quán)值的最小生成樹(shù)。5）測(cè)試數(shù)據(jù)生成數(shù)據(jù)之后檢驗(yàn)生成頂點(diǎn)數(shù)值是否介于 1020之

4、間；檢驗(yàn)各頂點(diǎn)間權(quán)值大 小是否介于2550間；同時(shí)檢驗(yàn)其自動(dòng)生成最小生成樹(shù)是否正確。三、概要設(shè)計(jì)1）抽象數(shù)據(jù)類型定義描述定義排序類sort ,將各個(gè)頂點(diǎn)按照其兩頂點(diǎn)之間權(quán)值大小排序，從大到小排 序，用到堆排序算法；定義帶權(quán)值的邊edge，分別存在start （起點(diǎn)）、end （終點(diǎn)）、value（權(quán)值） 三個(gè)變量；定義main類，調(diào)用sort、edge類與自身函數(shù)通過(guò)Kruskal函數(shù)實(shí)現(xiàn)最小生成 樹(shù)。2）功能模塊設(shè)計(jì)主函數(shù)隨機(jī)生成1020個(gè)頂點(diǎn)作為城市并同時(shí)生成任意兩頂點(diǎn)間 2550的權(quán) 值作為兩城市距離；在界面輸出隨機(jī)生成頂點(diǎn)個(gè)數(shù)及任意兩頂點(diǎn)間權(quán)值； 再調(diào)用 sort函數(shù)對(duì)權(quán)進(jìn)行排序，按照

5、權(quán)值的大小有小到大排序；排序之后實(shí)現(xiàn) Kruskal 函數(shù)，通過(guò)kruskal函數(shù)生成最小生成樹(shù)；最后輸出所生成的最小生成樹(shù)。3）模塊層次調(diào)用關(guān)系圖sortvoid siftvoid sortedgeint stallint eudintalueA四、詳細(xì)設(shè)計(jì)實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有的類的定義及類中成員函數(shù)，并對(duì)主要的模塊 寫出偽碼算法。1. 定義帶權(quán)值的邊及其三個(gè)變量start(起點(diǎn))、end (終點(diǎn))、value (權(quán)值)；定義該屬性為下邊的根據(jù)權(quán)值排序、Kruskal實(shí)現(xiàn)最小生成樹(shù)做下鋪墊；函數(shù)實(shí) 現(xiàn)如下：package tree;public class sort public sta

6、tic void sift(edge a, int root, int limit)int i = root;int j = i*2+1;/j 為i的左孩子while (j <= limit) /沿較小值孩子節(jié)點(diǎn)向下篩選if (j < limit && aj.getValue() < aj + 1.getValue()數(shù)組元素比較j+;/j為左右孩子的較小者if (aj.getValue() > ai.getValue() /若父親節(jié)點(diǎn)值較大edge e = ai;/孩子節(jié)點(diǎn)中較小值上移ai = aj;aj = e;i = j;j = i * 2 + 1

7、;/i、j 向下一層else break;/跳出循環(huán)public static void sort(edge data) int length = data.length;for (int i = length/2-1; i>=0; i-)創(chuàng)建最大堆sift(data, i, le ngth-1);for (int j = length - 1; j > 0; j-)每趟把最大值交換到后面字，再生成堆edge e = data0;data0 = dataj;dataj = e;sift(data, 0, j-1);2. 隨機(jī)生成介于1020之間個(gè)頂點(diǎn)作為各個(gè)城市，并同時(shí)生成任意兩頂

8、點(diǎn)間權(quán) 值，介于2550之間；每n個(gè)頂點(diǎn)之間最多生成n*(n-1)條邊；生成vertexNumber-1 個(gè)row (行)和row-1個(gè)column (列)可以防止同一個(gè)頂點(diǎn)生成自環(huán)；函數(shù)實(shí)現(xiàn)如下：int vertexNumber=( int )(Math. random()+1)*10)；System. out .println(”隨機(jī)生成"+vertexNumbe葉"個(gè)頂點(diǎn)");edge edges= n ewedgevertexNumber*(vertexNumber-1)/2;for (int row=0, index=0; row<vertexNu

9、mber; row+)/row 行、column列、index 數(shù)組for (int column=0; column<row; column+)int x=( int )(Math. random()+1)*25);/random隨機(jī)的edgesi ndex =n ewedge(row, colu mn, x);System.out .println(”頂點(diǎn)"+row+"和"+column+"之間的距離為"+x);in dex+;3. 定義排序類sort，按照堆排序函數(shù)對(duì)數(shù)組edge按照權(quán)值大小從小到大進(jìn)行排序（參照課本299頁(yè)）;pa

10、ckage tree;public class sort public static void sift(edge a, int root, int limit)int i = root;int j = i*2+1;/j 為i的左孩子while (j <= limit) /沿較小值孩子節(jié)點(diǎn)向下篩選if (j < limit && aj.getValue() < aj + 1.getValue()數(shù)組元素比較j+;/j為左右孩子的較小者if (aj.getValue() > ai.getValue() /若父親節(jié)點(diǎn)值較大edge e = ai;/孩子節(jié)點(diǎn)中

11、較小值上移ai = aj;aj = e;i = j;j = i * 2 + 1;/i、j 向下一層else break;/跳出循環(huán)public static void sort(edge data)int length = data.length;for (int i = length/2-1; i>=0; i-)/創(chuàng)建最大堆sift (data, i, length-1);for (int j = length - 1; j > 0; j-)/每趟把最大值交換到后面字,再生成堆edge e = dataO;dataO = dataj;dataj = e;sift (data, 0

12、, j-1);4.Kruskal方法實(shí)現(xiàn)最小生成樹(shù)。Kruskal 方法與Prim方法都是基于最小生成樹(shù)的 MS性質(zhì)：設(shè)G(V,E)是一個(gè) 聯(lián)通帶權(quán)無(wú)向圖，TV是頂點(diǎn)集合V的一個(gè)非空真子集。若(tv，v)包含于E是一 條權(quán)值最小的邊，其中tv包含于TV, v包含于V-TV,則必定存在G的一棵最小生成 樹(shù)T,T包含邊(tv,v)。其Kruskal算法參照課本334頁(yè)。其算法如下：int a = new int vertexNumber;/初始時(shí)刻，所有頂點(diǎn)的連通分量編號(hào)為-1，表示所有頂點(diǎn)都屬于一個(gè)獨(dú)立的連通分量for (int i = 0; i<a.length; i+) ai = -1

13、;edge result = n ewedgevertexNumber-1;/該數(shù)組用于記錄最小生成樹(shù) int temp = 0;for (edge e : edges)int start = e.getStart(); int end = e.getEnd();if (astart=aend && aend=-1) astart = ae nd = temp; resulttemp = e; temp+; else if (astart != aend) if (astart = -1) astart = ae nd;else if (aend = -1) ae nd = a

14、start;else int t = astart;for (int i = 0; i < vertexNumber; i+) if (ai = t) ai = ae nd;resulttemp = e;temp+;五、調(diào)試分析包括調(diào)試過(guò)程中遇到的問(wèn)題及解決的方法、算法的時(shí)間空間復(fù)雜性分析、 經(jīng)驗(yàn)體會(huì)。Sort 排序類算法時(shí)間復(fù)雜度為O(log2n)，Kruskal算法時(shí)間復(fù)雜度為0(1); 調(diào)試過(guò)程中，Kruskal算法實(shí)現(xiàn)出現(xiàn)問(wèn)題，剛開(kāi)始無(wú)法實(shí)現(xiàn)該函數(shù)，無(wú)法生 成最小生成樹(shù)；經(jīng)請(qǐng)教同學(xué)、查看資料、查看課本解決問(wèn)題。實(shí)現(xiàn)堆排序過(guò)程無(wú) 法實(shí)現(xiàn)，參考課本之后解得堆排序算法實(shí)現(xiàn)過(guò)程：調(diào)用si

15、ft ()方法n/2次，使得數(shù)據(jù)序列成為最大堆；對(duì)j=n-1，n-2.1 ，執(zhí)行下列n-1次完成排序操作：交 換根end0和元素endj，調(diào)用sift ()方法將endj的前j個(gè)元素調(diào)整成最大 堆。在編程過(guò)程中如遇難題可對(duì)其題目進(jìn)行認(rèn)真分析，然后參考課本或者其他資料已現(xiàn)有代碼亦或聞詢他人幫助，在自己查詢或者問(wèn)詢他人過(guò)程中也是自己學(xué)習(xí) 的過(guò)程，可以從中學(xué)習(xí)到很多知識(shí)。六、用戶使用說(shuō)明程序運(yùn)行后會(huì)自動(dòng)跳出1020個(gè)隨機(jī)頂點(diǎn)作為各個(gè)城市，同時(shí)隨機(jī)生成2550 的權(quán)值x，并生成此次所有頂點(diǎn)及其權(quán)值構(gòu)成的最小生成樹(shù)。七、測(cè)試結(jié)果1.生成0-12共13個(gè)頂點(diǎn):隨機(jī)生騎個(gè)頂點(diǎn)頂點(diǎn)二和0之間的距離笊K0 頂點(diǎn)

16、2和0之間的距離為2 § 頂點(diǎn)丄和二之間的距離芮丸, 頂點(diǎn)3和©之間的距離為北 頂點(diǎn)3和丄之閭的距離為30 頂點(diǎn)己和2之間的距離為處 頂點(diǎn)§和0之間的距離為24 頂點(diǎn)4和1之間的距禽為30 頂點(diǎn)弓和2之間的距離為2包 頂點(diǎn)4和勺之間的距離芮45 頂點(diǎn)5和0之間的距離為 頂點(diǎn)5和二之間的距離対20 頂點(diǎn)5和2之間的距離為£9 頂點(diǎn)5和3之閭的距離芮34 頂點(diǎn)5和4才間的距離為弓2 頂點(diǎn)宜和0之洵的距離為M5 頂雖和1之間的距離為3 5 頂點(diǎn)宕和2之間的距離為總總 頂點(diǎn)E和3之間的距離為弓4 頂點(diǎn)宜和4之間的距離為豈7 頂點(diǎn)E和5之間的距離為39 頂點(diǎn)：和。

17、之間的距離為3$ 頂點(diǎn)7和1之間的距離芮2丄 頂點(diǎn)：和2之間的距離為2 7 頂點(diǎn)丁和3之閭的距離対4巳 頂點(diǎn)7和弓之間的距離為弓專 頂點(diǎn)U和5之洵的距離対37頂點(diǎn)寸和£之間的延離黑H0 頂點(diǎn)£和0之間的距離為40 頂點(diǎn)總和丄之間的延離藥2宜 頂點(diǎn)E和2之間的距離為30 頂點(diǎn)3和3之間的距離為3總 頂雖和理之間的距離為42 頂點(diǎn)2和5之間的距離為 頂點(diǎn)2和總之間的證離為堆7 頂點(diǎn)E和U之間的距陽(yáng)為27 頂點(diǎn)9和0之間的涯離為30 頂點(diǎn)9和1之間的距離芮35 頂點(diǎn)9和丄之間的延離藥叮 頂點(diǎn)9和3之間的距離為29 頂點(diǎn)勺和咗之間的延離藥33 頂點(diǎn)9和5之冋的距離為25 頂點(diǎn)9和&

18、#163;之間的距離為23 頂點(diǎn)9*7 Z間的距離為29 頂點(diǎn)9和2之間的距離為處 頂點(diǎn)10和0之間的距離為32 頂點(diǎn)1G和1之閭的距離為弓總 頂點(diǎn)：0和2 Z間的距離為4 E 頂點(diǎn)工0和3之間的距離為35 頂點(diǎn)：0和4之閭的距廃対37 頂點(diǎn)10和5之間的距離為弓5 頂點(diǎn)：0和£之間的距離対27 頂點(diǎn)10和7之間的距離為日1 頂點(diǎn)丄0和3之閭的距盔為4二 頂點(diǎn):和9之間的距離為432.生成最小生成樹(shù)為：最小生咸樹(shù)芮：連接頂點(diǎn)號(hào)和占該邊的權(quán)值為25 連摟頂點(diǎn)2和0該邊的權(quán)值為2方 連接頂點(diǎn)豈和丄該邊的權(quán)值為2宜 連樓頂點(diǎn)7和2該邊的權(quán)值為27 連接頂臣2和：該邊的權(quán)值為丄丁 連接頂點(diǎn)丄

19、0和宜該邊的權(quán)值為2 = 連摟頂點(diǎn)5和0該邊的權(quán)值為27 連接頂點(diǎn)守和6該邊的權(quán)值為2昌 連接頂點(diǎn)電和2該邊的權(quán)值為 連接頂點(diǎn)今和3該邊的權(quán)值芮2日程序隨機(jī)自動(dòng)生成介于1020之間個(gè)頂點(diǎn)正確運(yùn)行，隨機(jī)自動(dòng)生成介于2550 之間權(quán)值正確運(yùn)行，使得任意兩頂點(diǎn)之間權(quán)值于 2550之間；經(jīng)驗(yàn)證該生成樹(shù)為 最小生成樹(shù)，程序運(yùn)行正確。最小生成樹(shù)定義：設(shè)G是一個(gè)帶權(quán)連通無(wú)向圖，w（ e）是邊e上的權(quán)，T是G 的生成樹(shù)，T中各邊的權(quán)值之和稱為生成樹(shù)T的權(quán)值或者代價(jià)（cost）。權(quán)值最小的生成樹(shù)稱之為最小生成樹(shù)(minimumcost spanning tree ),簡(jiǎn)稱最小生成樹(shù)。八、程序設(shè)計(jì)源代碼packa

20、ge tree;public class sort public static void sift(edge a, int root, int limit)int i = root;int j = i*2+1;/j 為i的左孩子while (j <= limit) /沿較小值孩子節(jié)點(diǎn)向下篩選if (j < limit && aj.getValue() < aj + 1.getValue()數(shù)組元素比較j+;/j為左右孩子的較小者if (aj.getValue() > ai.getValue() /若父親節(jié)點(diǎn)值較大edge e = ai;/孩子節(jié)點(diǎn)中較小值

21、上移ai = aj;aj = e;i = j;j = i * 2 + 1;/i、j 向下一層else break;/跳出循環(huán)public static void sort(edge data)int length = data.length;for (int i = length/2-1; i>=0; i-)/創(chuàng)建最大堆sift (data, i, length-1);for ( int j = length - 1; j > 0; j-)每趟把最大值交換到后面字,再生成堆edge e = data0;data0 = dataj;dataj = e;sift (data, 0, j

22、-1);package tree;public class edge private int start, end, value;/定義開(kāi)始、結(jié)束、權(quán)值public edge( int start, int end, int value)this .start=start;this .end=end;this .value=value;public int getStart() return start;public void setStart( int start) this .start = start;public int getEnd() return end;public void

23、setEnd( int end) this .end = end;public int getValue() return value;public void setValue( int value) this .value = value; package tree;public class mainpublic static void main(String args)int vertexNumber=( int )(Math. random()+1)*10); System. out .println(”隨機(jī)生成"+vertexNumbe葉"個(gè)頂點(diǎn)");ed

24、ge edges= n ewedgevertexNumber*(vertexNumber-1)/2;for (int row=0, index=0; row<vertexNumber; row+) /row 行、column列、index 數(shù)組for (int column=0; column<row; column+)int x=( int )(Math. random()+1)*25);/random隨機(jī)的edgesi ndex =n ewedge(row, colu mn, x);System.out .println(”頂點(diǎn)"+row+"和"+

25、column+"之間的距離為"+x);in dex+;sort. sort (edges);/ 對(duì)數(shù)組edges中的值進(jìn)行堆排序 int a = new int vertexNumber;for (int i = 0; i<a.length; i+)/初始時(shí)刻，所有頂點(diǎn)的連通分量編號(hào)為 -1，表示所有頂點(diǎn)都屬于 一個(gè)獨(dú)立的連通分量ai = -1;ai的值表示第i個(gè)頂點(diǎn)所屬的連通分量編號(hào)/該數(shù)組用于記錄最小生成樹(shù)edge result = n ewedgevertexNumber-1;int temp = 0;for (edge e : edges)int start

26、= e.getStart();int end = e.getEnd();if (astart=aend && aend=-1)只要將要加入 result 的edges的兩個(gè)頂點(diǎn)相等都為-1，/說(shuō)明不和result中的已經(jīng)加入的聯(lián)通分量有關(guān)系，則可以直 接加入result。astart = ae nd = temp;resulttemp = e;temp+;else if (astart != aend)if (astart = -1)/start=-1為懸空頂點(diǎn)，那么就讓 start=end，使加入的連通分量和其連接的result中連通分量的標(biāo)識(shí)統(tǒng)一。astart = ae n

27、d;else if (aend = -1)end=-1為懸空頂點(diǎn)，那么就讓 end=start，使加入的連通 分量和其連接的result中連通分量的標(biāo)識(shí)統(tǒng)一。ae nd = astart;else int t = astart;for (int i = 0; i < vertexNumber; i+)/要加入的edges使得result中的兩個(gè)不同的連通分量連接起 來(lái)，需將一個(gè)和另外一個(gè)進(jìn)行統(tǒng)一/遍歷所有的頂點(diǎn)如果值和start相等就都等于end,則兩個(gè)連通 分量進(jìn)行了統(tǒng)一if (ai = t)ai = ae nd;resulttemp = e;得到了 resulttemp+;/Syst

28、em.out.println(”");/System.out.pri ntln( Arrays.toStri ng(a);if (temp = vertexNumber-1)break;System. out .pri ntl n(”最小生成樹(shù)為：");for (edge e : result)System. out .pri ntl n(”連接頂點(diǎn)"+e.getStart()+" 和"+e.getEnd()+"該邊的權(quán)值為"+e.getValue();Whe n you are old and grey and full of sleep,And no ddi ng by the fire, take dow n this book,And slowly read, and dream of the soft lookYour eyes had once, and of their shadows deep;How many loved your mome nt