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

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

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

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

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

5、權(quán)值的大小有小到大排序；排序之后實現(xiàn) Kruskal 函數(shù)，通過kruskal函數(shù)生成最小生成樹；最后輸出所生成的最小生成樹。3）模塊層次調(diào)用關系圖sortvoid siftvoid sortedgeint stallint eudintalueA四、詳細設計實現(xiàn)概要設計中定義的所有的類的定義及類中成員函數(shù)，并對主要的模塊 寫出偽碼算法。1. 定義帶權(quán)值的邊及其三個變量start(起點)、end (終點)、value (權(quán)值)；定義該屬性為下邊的根據(jù)權(quán)值排序、Kruskal實現(xiàn)最小生成樹做下鋪墊；函數(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é)點向下篩選if (j < limit && aj.getValue() < aj + 1.getValue()數(shù)組元素比較j+;/j為左右孩子的較小者if (aj.getValue() > ai.getValue() /若父親節(jié)點值較大edge e = ai;/孩子節(jié)點中較小值上移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. 隨機生成介于1020之間個頂點作為各個城市，并同時生成任意兩頂

8、點間權(quán) 值，介于2550之間；每n個頂點之間最多生成n*(n-1)條邊；生成vertexNumber-1 個row (行)和row-1個column (列)可以防止同一個頂點生成自環(huán)；函數(shù)實現(xiàn)如下：int vertexNumber=( int )(Math. random()+1)*10)；System. out .println(”隨機生成"+vertexNumbe葉"個頂點");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隨機的edgesi ndex =n ewedge(row, colu mn, x);System.out .println(”頂點"+row+"和"+column+"之間的距離為"+x);in dex+;3. 定義排序類sort，按照堆排序函數(shù)對數(shù)組edge按照權(quán)值大小從小到大進行排序（參照課本299頁）;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é)點向下篩選if (j < limit && aj.getValue() < aj + 1.getValue()數(shù)組元素比較j+;/j為左右孩子的較小者if (aj.getValue() > ai.getValue() /若父親節(jié)點值較大edge e = ai;/孩子節(jié)點中

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

13、;edge result = n ewedgevertexNumber-1;/該數(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)試過程中遇到的問題及解決的方法、算法的時間空間復雜性分析、 經(jīng)驗體會。Sort 排序類算法時間復雜度為O(log2n)，Kruskal算法時間復雜度為0(1); 調(diào)試過程中，Kruskal算法實現(xiàn)出現(xiàn)問題，剛開始無法實現(xiàn)該函數(shù)，無法生 成最小生成樹；經(jīng)請教同學、查看資料、查看課本解決問題。實現(xiàn)堆排序過程無 法實現(xiàn)，參考課本之后解得堆排序算法實現(xiàn)過程：調(diào)用si

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

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

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

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

19、0和宜該邊的權(quán)值為2 = 連摟頂點5和0該邊的權(quán)值為27 連接頂點守和6該邊的權(quán)值為2昌 連接頂點電和2該邊的權(quán)值為 連接頂點今和3該邊的權(quán)值芮2日程序隨機自動生成介于1020之間個頂點正確運行，隨機自動生成介于2550 之間權(quán)值正確運行，使得任意兩頂點之間權(quán)值于 2550之間；經(jīng)驗證該生成樹為 最小生成樹，程序運行正確。最小生成樹定義：設G是一個帶權(quán)連通無向圖，w（ e）是邊e上的權(quán)，T是G 的生成樹，T中各邊的權(quán)值之和稱為生成樹T的權(quán)值或者代價（cost）。權(quán)值最小的生成樹稱之為最小生成樹(minimumcost spanning tree ),簡稱最小生成樹。八、程序設計源代碼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é)點向下篩選if (j < limit && aj.getValue() < aj + 1.getValue()數(shù)組元素比較j+;/j為左右孩子的較小者if (aj.getValue() > ai.getValue() /若父親節(jié)點值較大edge e = ai;/孩子節(jié)點中較小值

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;/定義開始、結(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(”隨機生成"+vertexNumbe葉"個頂點");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隨機的edgesi ndex =n ewedge(row, colu mn, x);System.out .println(”頂點"+row+"和"+

25、column+"之間的距離為"+x);in dex+;sort. sort (edges);/ 對數(shù)組edges中的值進行堆排序 int a = new int vertexNumber;for (int i = 0; i<a.length; i+)/初始時刻，所有頂點的連通分量編號為 -1，表示所有頂點都屬于 一個獨立的連通分量ai = -1;ai的值表示第i個頂點所屬的連通分量編號/該數(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的兩個頂點相等都為-1，/說明不和result中的已經(jīng)加入的聯(lián)通分量有關系，則可以直 接加入result。astart = ae nd = temp;resulttemp = e;temp+;else if (astart != aend)if (astart = -1)/start=-1為懸空頂點，那么就讓 start=end，使加入的連通分量和其連接的result中連通分量的標識統(tǒng)一。astart = ae n

27、d;else if (aend = -1)end=-1為懸空頂點，那么就讓 end=start，使加入的連通 分量和其連接的result中連通分量的標識統(tǒng)一。ae nd = astart;else int t = astart;for (int i = 0; i < vertexNumber; i+)/要加入的edges使得result中的兩個不同的連通分量連接起 來，需將一個和另外一個進行統(tǒng)一/遍歷所有的頂點如果值和start相等就都等于end,則兩個連通 分量進行了統(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(”最小生成樹為：");for (edge e : result)System. out .pri ntl 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