數(shù)據(jù)結(jié)構(gòu)-最小生成樹克魯斯卡爾算法的實(shí)現(xiàn)資料.doc

摘 要設(shè)計了一個用C/C+編寫程序?qū)崿F(xiàn)克魯斯卡爾最小生成樹算法，該程序操作簡單，界面清晰，易于為用戶所接受。關(guān)鍵詞：克魯斯卡爾，鄰接矩陣，最小生成樹，vc+。目 錄1 課題描述12 問題分析和任務(wù)定義23 邏輯設(shè)計34 詳細(xì)設(shè)計45 程序編碼106 程序調(diào)試與測試167 結(jié)果分析188 總結(jié)19參考文獻(xiàn)201課題描述用C/C+編寫程序?qū)崿F(xiàn)克魯斯卡爾最小生成樹算法。假設(shè)要在n個城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通n個城市只需要n-1條線路。這是我們設(shè)計一個最小生成樹的程序用來算出最節(jié)省經(jīng)費(fèi)的前提下建立這個通信站。112問題分析和任務(wù)定義 假設(shè)連通網(wǎng)N=（V,E）,則令最小生成樹的初始狀態(tài)為只有n個頂點(diǎn)而無邊的非連通圖T=(V,)，圖中每個頂點(diǎn)自成一個連通分量。在E中選擇代價最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中，否則舍去此邊而選擇下一條代價最小的邊。依次類推，直到T中所有頂點(diǎn)都在同一連通分量上為止。203邏輯設(shè)計設(shè)計思想： 采用鄰接矩陣來存儲圖，然后采用克魯斯卡爾算法求出最小生成樹。結(jié)構(gòu)體定義函數(shù)模塊二（求最小生成樹）克魯斯卡爾算法函數(shù)模塊一（圖的創(chuàng)建）采用鄰接矩陣做存儲結(jié)構(gòu)主函數(shù)引用函數(shù)模塊一、二，實(shí)現(xiàn)算法設(shè)計1）定義結(jié)構(gòu)體。2）采用鄰接矩陣做存儲結(jié)構(gòu)創(chuàng)建圖（函數(shù)模塊一）。3）采用克魯斯卡爾算法求出該圖的最小生成樹（函數(shù)模塊二）。4）在主函數(shù)里面分別調(diào)用以上各個函數(shù)，最終實(shí)現(xiàn)設(shè)計目的。4詳細(xì)設(shè)計4.1程序結(jié)構(gòu)函數(shù)CreateMGraph用來實(shí)現(xiàn)圖的創(chuàng)建，以及圖的相關(guān)信息的存儲。圖的存儲采用鄰接矩陣存儲結(jié)構(gòu)。函數(shù)minitree_KRUSKAL 用來求圖的最小生成樹。圖的最小生成樹有普利姆算法和克魯斯卡爾算法可以實(shí)現(xiàn)，本段代碼使用的是克魯斯卡爾算法，這也是本題所要求使用的。各個函數(shù)間的聯(lián)系先調(diào)用函數(shù)CreateMGraph實(shí)現(xiàn)圖的創(chuàng)建，然后調(diào)用函數(shù)minitree_KRUSKAL求出該圖的最小生成樹4.2設(shè)計說明在開始的時候添加一些限制條件方便函數(shù)的功能實(shí)現(xiàn)例如：#define MaxVertexNum 100 /最大頂點(diǎn)個數(shù)#define QueueSize 30 #define M 30模塊一：圖的創(chuàng)建結(jié)構(gòu)體定義為：typedef structVertexType vexsMaxVertexNum;/頂點(diǎn)表 Link edgesMaxVertexNumMaxVertexNum; /圖中當(dāng)前的相連接的兩個頂點(diǎn)int n,e;/圖中當(dāng)前的頂點(diǎn)數(shù)和邊數(shù)MGraph;函數(shù)定義為：MGraph CreateMGraph()MGraph G;int i,j,k,ch3; char ch1,ch2; printf(請輸入該圖的頂點(diǎn)數(shù)和邊數(shù):n); scanf(%d,%d,&(G.n),&(G.e); printf(請輸入該圖的頂點(diǎn)信息:n); for(i=1;i=G.n;i+) getchar();scanf(%c,&(G.vexsi); for(i=1;i=G.n;i+) for(j=1;j=G.n;j+) G.edgesij.w=0;printf(請輸入該圖每條邊對應(yīng)的兩個頂點(diǎn)的名稱:n); for(k=1;k=G.e;k+) scanf(%c,&ch1); printf(請輸入第%d條邊的頂點(diǎn)序號：,k); scanf(%c %c,&ch1,&ch2);printf(請輸入第%d條邊的權(quán)值大?。?k); scanf(%d,&ch3); for(i=1;ch1!=G.vexsi;i+); for(j=1;ch2!=G.vexsj;j+);ep.vexh=i;ep.vext=j; ep.weight=G.edgesij.w=ch3; /權(quán)值 ep.flag=0;p+; return G;流程如圖4.1所示創(chuàng)建圖使用的是函數(shù)MGraph CreateMGraph()，該圖的存儲結(jié)構(gòu)是鄰接矩陣，先對圖的結(jié)構(gòu)體進(jìn)行定義，再進(jìn)行初始化。在函數(shù)中需要手動輸入圖的參數(shù)（如頂點(diǎn)數(shù)、邊數(shù)、頂點(diǎn)信息、相連接的頂點(diǎn)、邊的權(quán)值等）用來建立圖并且確定圖的鄰接矩陣。最后在完成圖的信息輸入即建立圖以后輸出圖的鄰接矩陣表。模塊二：求圖的最小生成樹。void minitree_KRUSKAL(MGraph *G) int i,min,j,k;VEX tM; for(i=1;in;i+)ti.data=G-vexsi;ti.jihe=i;i=1; while (in) min=MaxVertexNum; for (j=0;je;j+) if (ej.weightmin&ej.flag=0) min=ej.weight; k=j; if (tek.vexh.jihe!=tek.vext.jihe) ek.flag=1; for (j=1;jn;j+) if (tj.jihe=tek.vext.jihe) tj.jihe=tek.vexh.jihe; tek.vext.jihe=tek.vexh.jihe; i+; else ek.flag=2; printf(克魯斯卡爾最小生成樹：n);for (i=0;ie;i+) if (ei.flag=1) printf(%d,%d) %dn,ei.vexh,ei.vext,ei.weight);/輸出最小生成樹該步驟應(yīng)用的是克魯斯卡爾算法，它的基本思想是：每次選不屬于同一連通分量(保證不生成圈)且邊權(quán)值最小的頂點(diǎn)，將邊加入MST（Minimum Spanning Tree最小生成樹），并將所在的2個連通分量合并，直到只剩一個連通分量。 流程如圖4.2所示。圖4.1圖4.25 程序編碼#include #define MaxVertexNum 100 /最大頂點(diǎn)個數(shù)#define M 30typedef enumFALSE,TRUEBoolean;Boolean visitedMaxVertexNum; /訪問標(biāo)志數(shù)組typedef char VertexType;typedef int EdgeType;typedef struct Lnodeint w;/相應(yīng)一條邊的權(quán)值Link;typedef structVertexType vexsMaxVertexNum;/頂點(diǎn)表 Link edgesMaxVertexNumMaxVertexNum; /圖中當(dāng)前的相連接的兩個頂點(diǎn)int n,e;/圖中當(dāng)前的頂點(diǎn)數(shù)和邊數(shù)MGraph; typedef struct char data; int jihe; VEX; typedef struct int vexh,vext;/邊頂點(diǎn) int weight;/權(quán)值int flag;/標(biāo)記EDGE; EDGE eM; int p=0;/*圖鄰接矩陣的建立*/ MGraph CreateMGraph()MGraph G;int i,j,k,ch3; char ch1,ch2; printf(請輸入該圖的頂點(diǎn)數(shù)和邊數(shù):n); scanf(%d,%d,&(G.n),&(G.e); while(G.e(G.n-1)*G.n/2)printf(輸入錯誤,請重新輸入:n); scanf(%d,%d,&(G.n),&(G.e); printf(請輸入該圖的頂點(diǎn)信息:n); for(i=1;i=G.n;i+) getchar();scanf(%c,&(G.vexsi); for(i=1;i=G.n;i+) for(j=1;j=G.n;j+) G.edgesij.w=0;printf(請輸入該圖每條邊對應(yīng)的兩個頂點(diǎn)的名稱:n); for(k=1;k=G.e;k+) scanf(%c,&ch1); printf(請輸入第%d條邊的頂點(diǎn)序號：,k); scanf(%c %c,&ch1,&ch2);printf(請輸入第%d條邊的權(quán)值大小：,k); scanf(%d,&ch3); for(i=1;ch1!=G.vexsi;i+); for(j=1;ch2!=G.vexsj;j+);ep.vexh=i;ep.vext=j; ep.weight=G.edgesij.w=ch3; /權(quán)值 ep.flag=0;p+; return G;/*克魯斯卡爾最小生成樹*/ void minitree_KRUSKAL(MGraph *G) int i,min,j,k;VEX tM; for(i=1;in;i+)ti.data=G-vexsi;ti.jihe=i;i=1; while (in) min=MaxVertexNum; for (j=0;je;j+) if (ej.weightmin&ej.flag=0) min=ej.weight; k=j; if (tek.vexh.jihe!=tek.vext.jihe) ek.flag=1; for (j=1;jn;j+) if (tj.jihe=tek.vext.jihe) tj.jihe=tek.vexh.jihe; tek.vext.jihe=tek.vexh.jihe; i+; else ek.flag=2; printf(克魯斯卡爾最小生成樹：n);for (i=0;ie;i+) if (ei.flag=1) printf(%d,%d) %dn,ei.vexh,ei.vext,ei.weight);/輸出最小生成樹 /*主函數(shù)調(diào)用*/ int main() MGraph G;printf(n);printf(*n); printf(* 克魯斯卡爾算法求圖的最小生成樹 *n);printf(*n); G=CreateMGraph();/建立該圖的鄰接矩陣minitree_KRUSKAL(&G);/克魯斯卡爾算法最小生成樹 return 0; 6 程序調(diào)試與測試運(yùn)行程序后如圖所示 圖6.1輸入錯誤數(shù)組后如圖所示 圖6.2繼續(xù)輸入正確數(shù)組后如圖所示 圖6.37 結(jié)果分析程序運(yùn)行時如果輸入的點(diǎn)大于邊減一再乘以邊除以2，那就是說輸入的數(shù)組是錯誤的，此時程序提醒輸入錯誤，在重新輸入。如果輸入正確那么程序會輸出最小生成樹。8 總結(jié)這個程序運(yùn)用函數(shù)CreateMGraph來實(shí)現(xiàn)圖的創(chuàng)建，以及圖的相關(guān)信息的存儲。圖的存儲采用鄰接矩陣存儲結(jié)構(gòu)。在運(yùn)用函數(shù)minitree_KRUSKAL來求圖的最小生成樹。圖的最小生成樹有普利姆算法和克魯斯卡爾算法可以實(shí)現(xiàn)，本段代碼使用的是克魯斯卡爾算法，這也是本題所要求使用的。在整個程序中先調(diào)用函數(shù)CreateMGraph實(shí)現(xiàn)圖的創(chuàng)