最小生成樹-課程設計報告

課程設計報告問題描述:已知一個無向連通網表示n個城市以及城市間可能設置的通信線路，其中網的頂點表示城市，邊表示兩個城市之間的線路，賦于邊上的權值表示相應的代價。對于n個點的連通網能建立許多不同的生成樹，每一棵生成樹都可以是一個通信網。我們要選擇一棵生成樹，使總的耗費最小

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