基于c語(yǔ)言的最小生成樹(shù)kruskal算法問(wèn)題-在線瀏覽
2025-01-11 06:26本頁(yè)面
【正文】 (edge *, int, int)。 Garc[i][j].adj = Garc[j][i].adj = 0。 i = Garum。//將輸入的頂點(diǎn)記錄為 1 getchar()。 printf(鄰接矩陣為 :\n)。 以上是圖的創(chuàng)建，鄰接矩陣的建立將 輔助權(quán)值排序 void MiniSpanTree(MGraph *G)//生成最小生成樹(shù) { } sort(edges, G)。 for (i = 1。 i++)//核心部分 { n = Find(parent, edges[i].begin)。 if (n != m)//判斷是否有回路，如果有，舍棄 { parent[m] = n。 } } } int Find(int *parent, int f)//找尾 { while ( parent[f] 0) { f = parent[f]。 關(guān)鍵代碼輸出最小生成樹(shù) 以下是主函數(shù)部門(mén) int main(void)//主函數(shù) { MGraph *G。 if (G == NULL) { printf(memory allcation failed,goodbye)。 } CreatGraph(G)。 system(pause)。 } 主函數(shù)通過(guò)調(diào)用不同的函數(shù)模塊來(lái)實(shí)現(xiàn)的功能 以下是函數(shù)關(guān)系的調(diào)用圖 Main( ) ________________________________ CreatGraph() MiniSpanTree( ) ________________ Sort ( ) Find( ) Swapn( ) 1 由于對(duì)函數(shù)調(diào)用關(guān)系不是非常清楚，導(dǎo)致在程序設(shè)計(jì)的時(shí)候思路不是非常的清晰 2 該程序只能滿足圖頂點(diǎn)比較少的最小生成樹(shù)的實(shí)現(xiàn)，如果 用戶要求更大的空間，可以在創(chuàng)建圖的時(shí)候開(kāi)辟更大的空間。這也是程序應(yīng)該改進(jìn)的地方?？臻g復(fù)雜度為 S（ N2） 4 在求最小生成樹(shù)函數(shù)中，對(duì)邊進(jìn)行標(biāo)記的時(shí)間復(fù)雜度為 O(N2)。 1,輸入圖的頂點(diǎn)數(shù)和變數(shù) 2 任意輸入兩個(gè)圖中連接的頂點(diǎn) 3 輸入這兩個(gè)頂點(diǎn)的權(quán)值 具體步驟圖如下 輸入完數(shù)據(jù)之后，按 enter 鍵將會(huì)顯示以下結(jié)果 最后按任意鍵退出，可以進(jìn)行其他圖最小生成樹(shù)的實(shí)現(xiàn) 這里提供其他幾組測(cè)試數(shù)據(jù)： 輸入的數(shù)據(jù)： 輸出數(shù)據(jù) 輸入數(shù)據(jù)： 輸出數(shù)據(jù)： ；源程序 《數(shù)據(jù)結(jié)構(gòu)》 課程設(shè)計(jì) 源代碼 （最小生成樹(shù) kruskal 算法的實(shí)現(xiàn)） 學(xué) 院 ： 東方科技學(xué)院 班 級(jí)： 08 級(jí) 信息工程 2 班 學(xué) 號(hào) ： 202041919234 姓 名： 譚詩(shī)琪 指導(dǎo)教師：
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1