最小生成樹-課程設(shè)計(jì)報(bào)告

課程設(shè)計(jì)報(bào)告問題描述:已知一個(gè)無向連通網(wǎng)表示n個(gè)城市以及城市間可能設(shè)置的通信線路，其中網(wǎng)的頂點(diǎn)表示城市，邊表示兩個(gè)城市之間的線路，賦于邊上的權(quán)值表示相應(yīng)的代價(jià)。對(duì)于n個(gè)點(diǎn)的連通網(wǎng)能建立許多不同的生成樹，每一棵生成樹都可以是一個(gè)通信網(wǎng)。我們要選擇一棵生成樹，使總的耗費(fèi)最小

需求分析：在N地建設(shè)網(wǎng)絡(luò)保證連通即可求最小的架設(shè)方式，任務(wù)完成可分為兩個(gè)部分：A存儲(chǔ)N中任意兩地之間的權(quán)（采用鄰接表，鄰接矩陣）B用prim和克魯斯卡爾兩種算法分別求出N地中最優(yōu)架設(shè)方式即最小生成樹。C按順序輸出生成樹中各條邊以及它們的權(quán)值。概要設(shè)計(jì)：程序分為兩大部分1存儲(chǔ)部分，2算法部分；存儲(chǔ)部分分為鄰接矩陣和鄰接表，而且包含了兩者直接的互相轉(zhuǎn)換；算法部分分為普里母算法和克魯斯卡爾算法。Prim算法的思想：假設(shè)V是圖中頂點(diǎn)的集合,E是圖中邊的集合,TE為最小生成樹中的邊的集合,則prim算法通過以下步驟可以得到最小生成樹:1:初始化:U={u0},TE={f}。此步驟設(shè)立一個(gè)只有結(jié)點(diǎn)u0的結(jié)點(diǎn)集U和一個(gè)空的邊集TE作為最小生成樹的初始形態(tài),在隨后的算法執(zhí)行中,這個(gè)形態(tài)會(huì)不斷的發(fā)生變化,直到得到最小生成樹為止。2:在所有u∈U,v∈V－U的邊(u,v)∈E中,找一條權(quán)最小的邊(u0,v0)，將此邊加進(jìn)集合TE中，并將此邊的非U中頂點(diǎn)加入U(xiǎn)中。此步驟的功能是在邊集E中找一條邊,要求這條邊滿足以下條件:首先邊的兩個(gè)頂點(diǎn)要分別在頂點(diǎn)集合U和V－U中,其次邊的權(quán)要最小。找到這條邊以后,把這條邊放到邊集TE中,并把這條邊上不在U中的那個(gè)頂點(diǎn)加入到U中。這一步驟在算法中應(yīng)執(zhí)行多次,每執(zhí)行一次,集合TE和U都將發(fā)生變化,分別增加一條邊和一個(gè)頂點(diǎn),因此,TE和U是兩個(gè)動(dòng)態(tài)的集合,這一點(diǎn)在理解算法時(shí)要密切注意。3:如果U=V,則算法結(jié)束;否則重復(fù)步驟2?？梢园驯静襟E看成循環(huán)終止條件。我們可以算出當(dāng)U=V時(shí),步驟2共執(zhí)行了n－1次(設(shè)n為圖中頂點(diǎn)的數(shù)目),TE中也增加了n－1條邊,這n－1條邊就是需要求出的最小生成樹的邊。用代碼實(shí)現(xiàn)為：voidMiniSpanTree_PRIM(MGraphG,VertexTypeu){//算法7.9//用普里姆算法從第u個(gè)頂點(diǎn)出發(fā)構(gòu)造網(wǎng)G的最小生成樹T，輸出T的各條邊。//記錄從頂點(diǎn)集U到V－U的代價(jià)最小的邊的輔助數(shù)組定義：//struct{//VertexTypeadjvex;//VRTypelowcost;//}closedge[MAX_VERTEX_NUM];inti,j,k;k=LocateVex(G,u);for(j=0;j<G.vexnum;++j){//輔助數(shù)組初始化if(j!=k){closedge[j].adjvex=u;closedge[j].lowcost=G.arcs[k][j].adj;}}closedge[k].lowcost=0;//初始，U＝{u}for(i=1;i<G.vexnum;++i){//選擇其余G.vexnum-1個(gè)頂點(diǎn)k=minimum(closedge);//求出T的下一個(gè)結(jié)點(diǎn)：第k頂點(diǎn)//此時(shí)closedge[k].lowcost=//MIN{closedge[vi].lowcost|closedge[vi].lowcost>0,vi∈V-U}printf(closedge[k].adjvex,G.vexs[k]);//輸出生成樹的邊closedge[k].lowcost=0;//第k頂點(diǎn)并入U(xiǎn)集for(j=0;j<G.vexnum;++j)if(G.arcs[k][j].adj<closedge[j].lowcost){//新頂點(diǎn)并入U(xiǎn)后重新選擇最小邊//closedge[j]={G.vexs[k],G.arcs[k][j].adj};closedge[j].adjvex=G.vexs[k];closedge[j].lowcost=G.arcs[k][j].adj;}}}//MiniSpanTree克魯斯卡爾算法的思想為：假設(shè)WN=(V,{E})是一個(gè)含有n個(gè)頂點(diǎn)的連通網(wǎng)，則按照克魯斯卡爾算法構(gòu)造最小生成樹的過程為：先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)，而邊集為空的子圖，若將該子圖中各個(gè)頂點(diǎn)看成是各棵樹上的根結(jié)點(diǎn)，則它是一個(gè)含有n棵樹的一個(gè)森林。之后，從網(wǎng)的邊集E中選取一條權(quán)值最小的邊，若該條邊的兩個(gè)頂點(diǎn)分屬不同的樹，則將其加入子圖，也就是說，將這兩個(gè)頂點(diǎn)分別所在的兩棵樹合成一棵樹；反之，若該條邊的兩個(gè)頂點(diǎn)已落在同一棵樹上，則不可取，而應(yīng)該取下一條權(quán)值最小的邊再試之。依次類推，直至森林中只有一棵樹，也即子圖中含有n-1條邊為止。詳細(xì)設(shè)計(jì)：(a)程序中結(jié)構(gòu)體定義：typedefstructEdgeType{ intu;//邊的起始頂點(diǎn) intv;//邊的終止頂點(diǎn) intw;//邊的權(quán)}EdgeType;//以下定義鄰接矩陣類型typedefstruct{intnunber;//頂點(diǎn)編號(hào)InfoTypeinfo;//頂點(diǎn)其他信息}VertexType;//頂點(diǎn)類型typedefstruct//圖的定義{intedges[maxv][maxv];//鄰接矩陣intn,e;//頂點(diǎn)數(shù)，弧數(shù)VertexTypevexs[maxv];//存放頂點(diǎn)信息}MGraph;//圖的鄰接矩陣類型//以下定義鄰接表類型typedefstructANode//弧的結(jié)點(diǎn)結(jié)構(gòu)類型{intadjvex;//該弧的終點(diǎn)位置InfoTypeinfo;//該弧的相關(guān)信息,這里用于存放權(quán)值structANode*nextarc;//指向下一條弧的指針}ArcNode;typedefstructVnode//鄰接表頭結(jié)點(diǎn)的類型{Vertexdata;//頂點(diǎn)信息intcount;//存放頂點(diǎn)入度,只在拓?fù)渑判蛑杏肁rcNode*firstarc;//指向第一條弧}VNode;typedefVNodeAdjList[maxv];//AdjList是鄰接表類型typedefstruct{AdjListadjlist;//鄰接表intn,e;//圖中頂點(diǎn)數(shù)n和邊數(shù)e}ALGraph;//圖的鄰接表類型(b)程序中用來實(shí)現(xiàn)鄰接矩陣和鄰接表存儲(chǔ)以及互相轉(zhuǎn)化的函數(shù)voidMatToList(MGraphg,ALGraph*&G)//將鄰接矩陣g轉(zhuǎn)換成鄰接表GvoidListToMat(ALGraph*G,MGraph&g)//將鄰接表G轉(zhuǎn)換成鄰接矩陣gvoidDispMat(MGraphg)//輸出鄰接矩陣gvoidDispAdj(ALGraph*G)//輸出鄰接表G起運(yùn)行結(jié)果為：(c)程序中用來完成prim和kriuskal算法的函數(shù)voidCreateMat(MGraph&g,intA[][maxv],intn)//輸入鄰接矩陣voidPrim(MGraphg,intv)//prim算法voidInsertSort(EdgeTypeE[],intn)//對(duì)E[0...n-1]按權(quán)值遞增有序的進(jìn)行直接插入排序voidKriuskal(MGraphg,intn)//克魯斯卡爾算法起運(yùn)行結(jié)果為：主函數(shù)模塊為：voidmain(){ inti,j,A[maxv][maxv],v0; MGraphg,g1;ALGraph*G; printf("說明：\n1首先應(yīng)該將N地有順序編號(hào)從0到(N-1)\n2其次在編號(hào)過程中已經(jīng)將0點(diǎn)標(biāo)記給任意選取的初始結(jié)點(diǎn)\n3運(yùn)行時(shí)以4地之間的無向有權(quán)圖為例如果還原成N地只需將代碼中注釋部分去掉\n\n\n\n");printf("輸入A[%d][%d]矩陣用來表示N地兩兩之間的權(quán)值:(0代表沒有邊)\n",maxv,maxv); /*for(i=0;i<maxv;i++)//輸入鄰接矩陣 for(j=0;j<maxv;j++) scanf("%d",&A[i][j]); printf("輸入起始頂點(diǎn)V0:\n"); scanf("%d",&v0);*/為了方便現(xiàn)將輸入注視掉，運(yùn)用以下數(shù)據(jù)進(jìn)行運(yùn)算v0=0;A[0][0]=0; A[0][1]=1;A[0][2]=2;A[0][3]=0;A[1][0]=1;A[1][1]=0;A[1][2]=3;A[1][3]=0;A[2][0]=2;A[2][1]=3;A[2][2]=0;A[2][3]=4;A[3][0]=0;A[3][1]=0;A[3][2]=4;A[3][3]=0;g.n=4;g.e=4;for(i=0;i<g.n;i++)for(j=0;j<g.n;j++)g.edges[i][j]=A[i][j];printf("\n");printf("您輸入的N地之間的鄰接矩陣:\n");DispMat(g);G=(ALGraph*)malloc(sizeof(ALGraph));printf("將N地的鄰接矩陣轉(zhuǎn)換成鄰接表存儲(chǔ):\n");MatToList(g,G);DispAdj(G);printf("將N地的鄰接表轉(zhuǎn)換成鄰接矩陣存儲(chǔ):\n");for(i=0;i<g.n;i++)for(j=0;j<g.n;j++)g1.edges[i][j]=0;ListToMat(G,g1);DispMat(g1);printf("\n");printf("用普里姆算法求得N地之間架設(shè)方法為:\n\n\n"); CreateMat(g,A,maxv); Prim(g,v0); printf("\n\n\n\n"); printf("用克魯斯卡爾算法求得N地之間架設(shè)方法為:\n\n\n");Kriuskal(g,g.e);}（d）調(diào)試分析：經(jīng)過努力，課程設(shè)計(jì)終于完成，由于我對(duì)數(shù)據(jù)結(jié)構(gòu)和c語言不是很了解，有時(shí)忽略了一些關(guān)鍵的細(xì)節(jié)，使得在編寫程序的過程中出現(xiàn)了一些問題。對(duì)于打字有時(shí)粗心導(dǎo)致出現(xiàn)一些難以發(fā)現(xiàn)的小錯(cuò)誤，在我們的耐心，細(xì)致的調(diào)試下最終使得程序能夠運(yùn)行，課程設(shè)計(jì)完滿完工測(cè)試數(shù)據(jù)是一個(gè)二元數(shù)組A其具體賦值為：A[0][0]=0; A[0][1]=1;A[0][2]=2;A[0][3]=0;A[1][0]=1;A[1][1]=0;A[1][2]=3;A[1][3]=0;A[2][0]=2;A[2][1]=3;A[2][2]=0;A[2][3]=4;A[3][0]=0;A[3][1]=0;A[3][2]=4;A[3][3]=0;求的最小生成樹的結(jié)果為：Prim算法假設(shè)網(wǎng)中有N個(gè)頂點(diǎn)，則第一個(gè)進(jìn)行初始化的循環(huán)語句頻度為n，第二個(gè)循環(huán)語句的頻度為n-1。其中有兩個(gè)內(nèi)循環(huán)；由此普里母算法的時(shí)間復(fù)雜度為O(n2),與網(wǎng)中的邊數(shù)無關(guān)！克魯斯卡爾算法至多對(duì)e條邊各掃描一次時(shí)間復(fù)雜度為O（eloge）。（e）課程總結(jié)認(rèn)識(shí)：對(duì)于建立n地最小生成樹問題是將數(shù)據(jù)結(jié)構(gòu)的知識(shí)運(yùn)用于實(shí)現(xiàn)現(xiàn)實(shí)問題，在程序設(shè)計(jì)過程中對(duì)于我來說十分繁雜，我先后請(qǐng)教了4位老師才將每一塊的具體實(shí)現(xiàn)辦法理解了！搭建框架是十分必要的，只有有了框架才能在具體實(shí)現(xiàn)上一步一步的完成。在具體實(shí)現(xiàn)算法是出現(xiàn)了問題：例如prim算法實(shí)現(xiàn)的時(shí)候沒有辦法記錄起始點(diǎn)，再輸出邊的過程中出現(xiàn)錯(cuò)誤，經(jīng)過上網(wǎng)查閱資料才建立了數(shù)組point[]將其解決。再調(diào)試程序過程中也是相當(dāng)繁瑣，代碼寫完了但是運(yùn)行過程中出現(xiàn)了很多很錯(cuò)錯(cuò)誤，在運(yùn)用debug來觀測(cè)數(shù)據(jù)后才漸漸的將錯(cuò)誤解決。編寫程序是一件幸苦但又愉快的過程，在學(xué)完C語言是并沒有什么太多的算法思想，但數(shù)據(jù)結(jié)構(gòu)給了我很多靈感，有了數(shù)據(jù)結(jié)構(gòu)的思想很多實(shí)際問題就能解決了，主要由于代碼接觸太少，所以在有了思想的情況下很難實(shí)現(xiàn)代碼，以后要經(jīng)常去用代碼實(shí)現(xiàn)自己的想法，算法對(duì)于程序設(shè)計(jì)十分重要，數(shù)據(jù)結(jié)構(gòu)可以說是編程者的大腦，沒有數(shù)據(jù)結(jié)構(gòu)代碼就失去了運(yùn)用于實(shí)際問題的能力。心得：在課程設(shè)計(jì)的過程中收獲很多，獨(dú)立思考是我首先覺悟到的，因?yàn)槠鸪踉诳吹椒彪s的代碼滿腦子只有憤怒，自己根本沒有辦法實(shí)現(xiàn)，可后來在經(jīng)過上網(wǎng)查閱思想和數(shù)據(jù)結(jié)構(gòu)書我才慢慢的有了自己的想法。最后漸漸的喜歡上了代碼，課程設(shè)計(jì)的確讓我有一種成為編程人員的感覺了，經(jīng)過努力我終于完成了本次課程設(shè)計(jì)，通過這次課程設(shè)計(jì)，我感覺到要真正做出一個(gè)程序并不很容易，但只要用心去做，總會(huì)有收獲，特別是當(dāng)我遇到一個(gè)問題，想辦法去解決，最后終于找到方法時(shí)，心里的那份喜悅之情真是難以形容。編寫程序中遇到問題再所難免，應(yīng)耐心探究其中的原因，從出現(xiàn)問題的地方起，并聯(lián)系前后程序，仔細(xì)推敲，逐個(gè)排查。直到最終搞清為止。我們本次做的是圖的做小生成樹問題，深刻的體會(huì)到它的實(shí)用性。通過本次課程設(shè)計(jì)我們發(fā)現(xiàn)我們對(duì)于C語言和數(shù)據(jù)結(jié)構(gòu)還有很多地方不知道，今后需要努力學(xué)習(xí)。-------------------------------------------------------------------------------------------------------參考文獻(xiàn)：[1]李云清，楊慶紅.數(shù)據(jù)結(jié)構(gòu)（C語言版）.北京：人民郵電出版社，2004.[2]嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）.北京：清華大學(xué)出版.1997.[3]蘇光奎,李春葆.數(shù)據(jù)結(jié)構(gòu)導(dǎo)學(xué).北京:清華大學(xué)出版.2002.[4]周海英，馬巧梅，靳雁霞.數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì).北京：國防工業(yè)出版社，2007.[5]張海藩.軟件工程導(dǎo)論.北京：清華大學(xué)出版社.2003.[6]互聯(lián)網(wǎng)附錄：程序清單#include"stdafx.h"#include"stdlib.h"typedefintInfoType;typedefintVertex;#definemaxv4//圖的頂點(diǎn)數(shù)#defineinf100000000//兩頂點(diǎn)無相鄰邊時(shí)的權(quán)typedefstructEdgeType{ intu;//邊的起始頂點(diǎn) intv;//邊的終止頂點(diǎn) intw;//邊的權(quán)}EdgeType;//以下定義鄰接矩陣類型typedefstruct{intnunber;//頂點(diǎn)編號(hào)InfoTypeinfo;//頂點(diǎn)其他信息}VertexType;//頂點(diǎn)類型typedefstruct//圖的定義{intedges[maxv][maxv];//鄰接矩陣intn,e;//頂點(diǎn)數(shù)，弧數(shù)VertexTypevexs[maxv];//存放頂點(diǎn)信息}MGraph;//圖的鄰接矩陣類型//以下定義鄰接表類型typedefstructANode//弧的結(jié)點(diǎn)結(jié)構(gòu)類型{intadjvex;//該弧的終點(diǎn)位置InfoTypeinfo;//該弧的相關(guān)信息,這里用于存放權(quán)值structANode*nextarc;//指向下一條弧的指針}ArcNode;typedefstructVnode//鄰接表頭結(jié)點(diǎn)的類型{Vertexdata;//頂點(diǎn)信息intcount;//存放頂點(diǎn)入度,只在拓?fù)渑判蛑杏肁rcNode*firstarc;//指向第一條弧}VNode;typedefVNodeAdjList[maxv];//AdjList是鄰接表類型typedefstruct{AdjListadjlist;//鄰接表intn,e;//圖中頂點(diǎn)數(shù)n和邊數(shù)e}ALGraph;//圖的鄰接表類型//將鄰接矩陣g轉(zhuǎn)換成鄰接表GvoidMatToList(MGraphg,ALGraph*&G){inti,j,n=g.n;//n為頂點(diǎn)數(shù)ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;i<n;i++)//給鄰接表中所有頭結(jié)點(diǎn)的指針域置初值G->adjlist[i].firstarc=NULL;for(i=0;i<n;i++)//檢查鄰接矩陣中每個(gè)元素for(j=n-1;j>=0;j--)if(g.edges[i][j]!=0)//鄰接矩陣的當(dāng)前元素不為0{p=(ArcNode*)malloc(sizeof(ArcNode));//創(chuàng)建一個(gè)結(jié)點(diǎn)*pp->adjvex=j;p->info=g.edges[i][j];p->nextarc=G->adjlist[i].firstarc;//將*p鏈到鏈表后G->adjlist[i].firstarc=p;}G->n=n;G->e=g.e;}voidListToMat(ALGraph*G,MGraph&g)//將鄰接表G轉(zhuǎn)換成鄰接矩陣g{inti,n=G->n;ArcNode*p;for(i=0;i<n;i++){p=G->adjlist[i].firstarc;while(p!=NULL){g.edges[i][p->adjvex]=p->info;p=p->nextarc;}}g.n=n;g.e=G->e;}voidDispMat(MGraphg)//輸出鄰接矩陣g{inti,j;for(i=0;i<g.n;i++){for(j=0;j<g.n;j++)if(g.edges[i][j]==0)printf("%3s","∞");elseprintf("%3d",g.edges[i][j]);printf("\n");}}voidDispAdj(ALGraph*G)//輸出鄰接表G{inti;ArcNode*p;for(i=0;i<G->n;i++){p=G->adjlist[i].firstarc;printf("%3d:",i);while(p!=NULL){printf("%3d",p->adjvex);//輸出該弧的終點(diǎn)位置p=p->nextarc;}printf("\n");}}voidCreateMat(MGraph&,int[][maxv],int);voidPrim(MGraph,int);voidInsertSort(EdgeType[],int);voidKriuskal(MGraph,int);voidmain(){ inti,j,A[maxv][maxv],v0; MGraphg,g1;ALGraph*G; printf("說明：\n1首先應(yīng)該將N地有順序編號(hào)從0到(N-1)\n2其次在編號(hào)過程中已經(jīng)將0點(diǎn)標(biāo)記給任意選取的初始結(jié)點(diǎn)\n3運(yùn)行時(shí)以4地之間的無向有權(quán)圖為例如果還原成N地只需將代碼中注釋部分去掉\n\n\n\n");printf("輸入A[%d][%d]矩陣用來表示N地兩兩之間的權(quán)值:(0代表沒有邊)\n",maxv,maxv); /*for(i=0;i<maxv;i++)//輸入鄰接矩陣 for(j=0;j<maxv;j++) scanf("%d",&A[i][j]); printf("輸入起始頂點(diǎn)V0:\n"); scanf("%d",&v0);*/v0=0;A[0][0]=0; A[0][1]=1;A[0][2]=2;A[0][3]=0;A[1][0]=1;A[1][1]=0;A[1][2]=3;A[1][3]=0;A[2][0]=2;A[2][1]=3;A[2][2]=0;A[2][3]=4;A[3][0]=0;A[3][1]=0;A[3][2]=4;A[3][3]=0;g.n=4;g.e=4;for(i=0;i<g.n;i++)for(j=0;j<g.n;j++)g.edges[i][j]=A[i][j];printf("\n");printf("您輸入的N地之間的鄰接矩陣:\n");DispMat(g);G=(ALGraph*)malloc(sizeof(ALGraph));printf("將N地的鄰接矩陣轉(zhuǎn)換成鄰接表存儲(chǔ):\n");MatToList(g,G);DispAdj(G);printf("將N地的鄰接表轉(zhuǎn)換成鄰接矩陣存儲(chǔ):\n");for(i=0;i<g.n;i++)for(j=0;j<g.n;j++)g1.edges[i][j]=0;ListToMat(G,g1);DispMat(g1);printf("\n");printf("用普里姆算法求得N地之間架設(shè)方法為:\n\n\n"); CreateMat(g,A,maxv); Prim(g,v0); printf("\n\n\n\n"); printf("用克魯斯卡爾算法求得N地之間架設(shè)方法為:\n\n\n");Kriuskal(g,g.e);}voidCreateMat(MGraph&g,intA[][maxv],intn)//輸入鄰接矩陣{ inti,j; g.n=n; g.e=0; for(i=0;i<n;i++) for(j=0;j<n;j++) { if(A[i][j]!=0){ g.edges[i][j]=A[i][j]; g.e++; } else g.edges[i][j]=inf; } }voidPrim(MGraphg,intv){ inti,j,n=maxv; intmin; intpoint[maxv],key[maxv]; for(i=0;i<n;i++) { point[i]=v;//所有point均存有V key[i]=g.edges[v][i];//記錄所有以V為起點(diǎn)的邊的權(quán) } key[v]=0;//將起點(diǎn)V到V的權(quán)值設(shè)為0 for(i=1;i<n;i++) { min=inf; for(j=0;j<n;j++) if(key[j]>0&&key[j]<min) { v=j; min=key[j]; } printf("邊(%d,%d):%d\n\n\n",point[v],v,min); key[v]=0; for(j=0;j<n;j++) if(g.edges[v][j]<key[j]) { point[j]=v