最小生成樹及其算法

1、精選優(yōu)質(zhì)文檔-傾情為你奉上離散數(shù)學(xué)大作業(yè)論文題目： 最小生成樹及其算法 院 系： 電子工程學(xué)院 專 業(yè)： 智能科學(xué)與技術(shù) 學(xué) 號： 姓 名： 二零一一 年 十一 月專心-專注-專業(yè)摘 要連通圖廣泛應(yīng)用于交通建設(shè)，求連通圖的最小生成樹是最主要的應(yīng)用。比如要在n個城市間建立通信聯(lián)絡(luò)網(wǎng)，要考慮的是如何保證n點連通的前提下最節(jié)省經(jīng)費，就應(yīng)用到了最小生成樹。求圖的最小生成樹有兩種算法，一種是Prim（普里姆）算法，另一種是Kruskal（克魯斯卡爾）算法。本文主要介紹Prim（普里姆）算法及利用。本文從分析課題的題目背景、題目意義、題目要求等出發(fā)，分別從需求分析、總體設(shè)計、詳細設(shè)計、測試等各個方面詳細介

2、紹了系統(tǒng)的設(shè)計與實現(xiàn)過程，最后對系統(tǒng)的完成情況進行了總結(jié)。關(guān)鍵字：prum算法 最小生成樹 算法比較1.有關(guān)最小生成樹的概念最小生成樹：連通加權(quán)圖里權(quán)和最小的生成樹稱為最小生成樹。從最小生成樹定義看主要先了解圖、樹及生成樹。本文中最小生成樹在計算機中存儲方法是應(yīng)用鄰接矩陣的形式存儲。故也應(yīng)了解鄰接矩陣的定義。定義一（圖）：圖是有一個非空的頂點集合和一個描述頂點之間的關(guān)系即邊的集合組成。它可以形式化的定義為：G=(V,E)V= | VertexTypeE=|,VP(,)其中，G表示一個圖，V是圖G中頂點的集合，E是V中頂點偶對的有限集，這些頂點偶對稱為邊，VertexType是用于描述頂點類型，

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

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

5、是圖G的一棵生成樹。2.prim算法介紹從單一頂點開始，普里姆算法按照以下步驟逐步擴大樹中所含頂點的數(shù)目，直到遍及連通圖的所有頂點。1. 輸入：一個加權(quán)連通圖，其中頂點集合為V，邊集合為E；2. 初始化：Vnew = x，其中x為集合V中的任一節(jié)點（起始點），Enew = ；3. 重復(fù)下列操作，直到Vnew = V： 1. 在集合E中選取權(quán)值最小的邊（u, v），其中u為集合Vnew中的元素，而v則不是（如果存在有多條滿足前述條件即具有相同權(quán)值的邊，則可任意選取其中之一）；2. 將v加入集合Vnew中，將（u, v）加入集合Enew中；4. 輸出：使用集合Vnew和Enew來描述所得到的最小生

6、成樹。3.prim算法的實現(xiàn)#include#define TURE 999typedef struct ArcNodechar vexs10;int edgs1010;int n,e;MGraph;struct edgint v1;int v2;int cost;A10,B10;/創(chuàng)建圖void GreateMGraph(MGraph *G) int i,j,k,weight,m,n;int ch1,ch2;char a,b;printf(ntt輸入頂點數(shù)邊數(shù)(格式如:3 4):);scanf(%d %d,&(G-n),&(G-e); /輸入頂點數(shù),邊數(shù)for(i=0;in;i+)getch

7、ar();printf(ntt請輸入第%d個頂點:,i+1);scanf(%c,&(G-vexsi); /輸入頂點 for(i=0;in;i+)for(j=0;jn;j+)G-edgsij=0;for(k=0;ke;k+)/getchar();printf(ntt請輸入第%d條邊的頂點權(quán)值(格式如:i j):,k+1);getchar(); scanf(%c %c %d,&a,&b,&weight);/scanf(%c,&a);/getchar(); / scanf(%c,&b);m=0;n=0; for( m=0;G-vexsm!=a;m+); for( n=0;G-vexsn!=b;n+)

8、;/printf(ntt請輸入權(quán)值:);scanf(%d,&weight); ch1=m;ch2=n; G-edgsch1ch2=weight;G-edgsch2ch1=weight;void prim(MGraph *G, int v) int i,j,k,min; struct int adjvex; int lowcost; closedge10; for (i=0;in;i+) /初始化 closedgei.lowcost=G-edgsvi; closedgei.adjvex=v; closedgev.lowcost=TURE; for (i=1;in;i+) min=100; /*

9、100為允許的最大權(quán)值*/ for(j=0;jn;j+) if (closedgej.lowcost!=TURE & closedgej.lowcost!=0) if (closedgej.lowcostvexsclosedgek.adjvex, G-vexsk, min); closedgek.lowcost=TURE; for (j=0;jn;j+) if (closedgej.lowcost!=TURE) if(G-edgskjedgskj; closedgej.adjvex=k; void Kruskal(MGraph *G)int k=0,m=0,n=0;int vf1,vf2,mi

10、n,vset100;for(int i=0;in;i+)for(int j=0;jn;j+)if(G-edgsij!=0)if(iedgsij;k+;n=0;while(me-1)min=999;for(i=n;ik;i+)if(Ai.costmin)Bn.v1=Ai.v1;Bn.v2=Ai.v2;Bn.cost=An.cost;min=Ai.cost;n+;m+;for(i=0;in;i+)vseti=i;k=0;while(ke)vf1=Bk.v1;vf2=Bk.v2;if(vsetvf1!=vsetvf2)printf(%c,%c,%d),G-vexsBk.v1,G-vexsBk.v2,

11、Bk.cost);vsetvf2=vsetvf1;k+;int main(void)MGraph *G,a; char ch1;int choice;G=&a;printf(ntt建立圖的鄰接矩陣n); GreateMGraph(G); /* printf(ntt已建立一個鄰接矩陣！n);for(i=0;in;i+)printf(ntt);for(j=0;jn;j+)printf(%5d,G-edgsij);*/getchar();ch1=1;while(ch1=1)printf(n);printf(ntt 最小生成樹 );printf(ntt*);printf(ntt* 1prim算法 *)

12、;/printf(ntt* 2kruskal算法 *);printf(ntt* 0退 出 *);printf(ntt*);printf(ntt請選擇菜單號0-1：);scanf(%d,&choice);getchar();switch(choice)case 1: printf(nttprim算法輸出為：); prim(G,0);break;case 2:printf(nttKruskal算法輸出為：); Kruskal(G);break;case 0: ch1=0; break;default:printf(ntt輸入錯誤！請重新輸入!);return 0;4應(yīng)用prim算法的例子 如下圖所示的賦權(quán)圖表示某七個城市 及預(yù)先算出它們之間的一些直接通信成路造價（單位：萬元），試給出一個設(shè)計方案，使得