基于c語言的最小生成樹kruskal算法問題(編輯修改稿)
2024-12-14 06:26 本頁面
【文章內(nèi)容簡介】 找尾 { while ( parent[f] 0) { f = parent[f]。 } return f。 關(guān)鍵代碼輸出最小生成樹 以下是主函數(shù)部門 int main(void)//主函數(shù) { MGraph *G。 G = (MGraph*)malloc(sizeof(MGraph))。 if (G == NULL) { printf(memory allcation failed,goodbye)。 exit(1)。 } CreatGraph(G)。 MiniSpanTree(G)。 system(pause)。 return 0。 } 主函數(shù)通過調(diào)用不同的函數(shù)模塊來實現(xiàn)的功能 以下是函數(shù)關(guān)系的調(diào)用圖 Main( ) ________________________________ CreatGraph() MiniSpanTree( ) ________________ Sort ( ) Find( ) Swapn( ) 1 由于對函數(shù)調(diào)用關(guān)系不是非常清楚，導(dǎo)致在程序設(shè)計的時候思路不是非常的清晰 2 該程序只能滿足圖頂點比較少的最小生成樹的實現(xiàn)，如果 用戶要求更大的空間，可以在創(chuàng)建圖的時候開辟更大的空間。 3 在程序輸入的時候，必須頂點數(shù)值小 的先輸入，否則程序?qū)鲥e。這也是程序應(yīng)該改進的地方。 4 算法的時空分析 1，對矩陣的初始化 ，設(shè)輸入一個 n個頂點的圖，那個將要對矩陣的 nxn 個元素進行初始化，所以時間復(fù)雜度為 O(N2) 2,輸入權(quán)值和 邊的時間復(fù)雜度為 O(n),所以構(gòu)建圖的時間復(fù)雜度為 O(N2+N) O(N2) 。空間復(fù)雜度為 S（ N2） 4 在求最小生成樹函數(shù)中，對邊進行標記的時間復(fù)雜度為 O(N2)。對權(quán)值進行排序的時間復(fù)雜度為 O(N2)，對 parent 數(shù)組賦值的時間復(fù)雜度為 o(n),所以該函數(shù)的時間復(fù)雜度為 O（ 2N2+N） 5 過這次課程設(shè)計，一方面 我 加深對課內(nèi)所學(xué)的有關(guān)數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計和時空分析等課程基本內(nèi)容的理解，另一方面，使我在 序設(shè)計方法（如抽象數(shù)據(jù)類型、結(jié)構(gòu)化分析、模塊化設(shè)計和結(jié)構(gòu)化設(shè)計）、 C 語言程序調(diào)試和 測試方面受到比較系統(tǒng)的嚴格的訓(xùn)練。 1,輸入圖的頂點數(shù)和變數(shù) 2 任意輸入兩個圖中連接的頂點 3 輸入這兩個頂點的
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1