最小生成樹算法和算法

《最小生成樹算法和算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、....包頭師范學(xué)院本科學(xué)年論文論文題目：最小生成樹及其算法院系：數(shù)學(xué)科學(xué)學(xué)院專業(yè)：信息與計(jì)算科學(xué)學(xué)號(hào)：0800000062姓名：吉余指導(dǎo)教師：吳云撰寫學(xué)年：2010至2011學(xué)年二零一零年十一月專業(yè)資料....目錄1有關(guān)最小生成樹的概念12prim算法介紹23prim算法的實(shí)現(xiàn)34kruskal算法介紹85kruskal算法的實(shí)現(xiàn)96算法比較12參考文獻(xiàn)13專業(yè)資料....摘要連通圖廣泛應(yīng)用于交通建設(shè)，求連通圖的最小生成樹是最主要的應(yīng)用。比如要在n個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng)，要考慮的是如何保證n點(diǎn)連通的前提下最節(jié)省經(jīng)費(fèi)，

2、就應(yīng)用到了最小生成樹。求圖的最小生成樹有兩種算法，一種是Prim（普里姆）算法，另一種是Kruskal（克魯斯卡爾）算法。本文重點(diǎn)講述prum算法和kruskai算法和比較。本文從分析課題的題目背景、題目意義、題目要求等出發(fā)，分別從需求分析、總體設(shè)計(jì)、詳細(xì)設(shè)計(jì)、測(cè)試等各個(gè)方面詳細(xì)介紹了系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)過程，最后對(duì)系統(tǒng)的完成情況進(jìn)行了總結(jié)。關(guān)鍵字：prum算法、最小生成樹kruskal算法算法比較專業(yè)資料....1有關(guān)最小生成樹的概念最小生成樹：連通加權(quán)圖里權(quán)和最小的生成樹稱為最小生成樹。從最小生成樹定義看主要先了解圖、

3、樹及生成樹。本文中最小生成樹在計(jì)算機(jī)中存儲(chǔ)方法是應(yīng)用鄰接矩陣的形式存儲(chǔ)。故也應(yīng)了解鄰接矩陣的定義。定義一（圖）：圖是有一個(gè)非空的頂點(diǎn)集合和一個(gè)描述頂點(diǎn)之間的關(guān)系即邊的集合組成。它可以形式化的定義為：G=(V,E)V={

4、VertexType}E={<,>

5、,∈V∧P(,)?}其中，G表示一個(gè)圖，V是圖G中頂點(diǎn)的集合，E是V中頂點(diǎn)偶對(duì)的有限集，這些頂點(diǎn)偶對(duì)稱為邊，VertexType是用于描述頂點(diǎn)類型，集合E中P(,)的含義是：對(duì)有向圖來說用“<>”表示，對(duì)無向圖來說用“（）”表示，即從到兩個(gè)頂點(diǎn)之間存在邊。定義二（樹）

6、：樹包含n（n>=0）個(gè)節(jié)點(diǎn)。當(dāng)n=0時(shí)表示為空樹。其定義如下：T=(D,R)其中，D為樹中節(jié)點(diǎn)的有限集合，關(guān)系R滿足一下條件：1）有且僅有一個(gè)節(jié)點(diǎn)k0屬于D，它對(duì)于關(guān)系R來說沒有前趨節(jié)點(diǎn)，結(jié)點(diǎn)k0稱作樹的根結(jié)點(diǎn)。2）除根結(jié)點(diǎn)k0之外，D中的每個(gè)結(jié)點(diǎn)僅有一個(gè)前趨結(jié)點(diǎn)，但可以有過個(gè)后繼結(jié)點(diǎn)。3）D中可以有多個(gè)終端結(jié)點(diǎn)。即除根結(jié)點(diǎn)無父結(jié)點(diǎn)，其余各結(jié)點(diǎn)都有一個(gè)父結(jié)點(diǎn)和n（n>=0）個(gè)子結(jié)點(diǎn)。圖的矩陣表示，本文中只用到了鄰接矩陣，故在這只提出鄰接矩陣的定義，及其圖在鄰接矩陣中的表示。設(shè)圖A=(V,E)是一個(gè)有n個(gè)頂點(diǎn)的圖,圖的

7、鄰接矩陣是一個(gè)二維數(shù)組A.edge[n][n]，　　用來存放頂點(diǎn)的信息和邊或弧的信息。定義三（鄰接矩陣（AdjacencyMatrix））：是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是一個(gè)圖，其中V={v1,v2,…,vn}。G的鄰接矩陣是一個(gè)具有下列性質(zhì)的n階方陣：（本文主要為無向圖的鄰接矩陣）（1）無向圖的鄰接矩陣是對(duì)稱的;有向圖的鄰接矩陣可能是不對(duì)稱的。專業(yè)資料....（1）無向圖的鄰接矩陣中第i行第j列表示i結(jié)點(diǎn)到j(luò)結(jié)點(diǎn)的度即權(quán)值，可以表示為某一具體應(yīng)用的數(shù)據(jù)。也表示i結(jié)點(diǎn)是否與j結(jié)點(diǎn)連通。定義四（生成樹）

8、：如果T是G的一個(gè)生成子圖又是一棵樹，則稱T是圖G的一棵生成樹。2prim算法介紹最小生成樹的兩個(gè)著名算法：prim算法[和克魯斯卡爾算法[2],本文應(yīng)用的是prim算法。則克魯斯卡爾算法則不進(jìn)行描述了。Prim算法的基本思想：首先，選擇帶最小的邊，把它放進(jìn)生成樹里，相繼添加帶權(quán)最小的邊，這些邊與已在樹立的頂點(diǎn)相關(guān)聯(lián)，并且不與已在數(shù)理的邊形成圈，當(dāng)已經(jīng)添加了n-1條邊為止。PRIM算法介紹：設(shè)圖中頂點(diǎn)的全集為V,U中存放已選中過的點(diǎn),用數(shù)據(jù)結(jié)構(gòu)closedge[]存放選擇需要的數(shù)據(jù),先把下標(biāo)0對(duì)應(yīng)點(diǎn)放入U(xiǎn)中,close

9、dge[i].uxiabiao=0,(因?yàn)閁中只有下標(biāo)0這一個(gè)點(diǎn)),closedge[i].lowcost中存放其他點(diǎn)到下標(biāo)為0的點(diǎn)的權(quán),closedge[0].lowcost=0;表示下標(biāo)為0的點(diǎn)已在U中了。在closedge按順序找到最先不在U中,且與U中點(diǎn)直接相連的點(diǎn),把此邊的權(quán)賦給min，用擂臺(tái)式比較法選出closedge[j].lowcost中最小的,此時(shí)min中存放的是最小值所在下標(biāo),也就是下一個(gè)要放入U(xiǎn)中的點(diǎn)的下標(biāo)。輸出選中的這條邊，它是最小生成樹中的一條邊。因?yàn)閁中又加入了一個(gè)點(diǎn)，所以要修改closed

10、ge[i].lowcost的值，比較新選中點(diǎn)與V-U中點(diǎn)的權(quán)和原來的closedge[i].lowcost,取小的那個(gè)存入。然后繼續(xù)如上的選擇,循環(huán)vexnum-1次,就選出了最小生成樹中的vexnum-1條邊。本程序采用數(shù)組存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)，把第一個(gè)點(diǎn)所到的邊記錄下來，然后把權(quán)值最小的邊存入數(shù)組，同時(shí)將剛才所存邊的的終點(diǎn)作為起點(diǎn)