數據結構-最小生成樹克魯斯卡爾算法的實現資料.doc

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