基于c語言的最小生成樹kruskal算法問題(編輯修改稿)
2025-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ù)模塊來實(shí)現(xiàn)的功能 以下是函數(shù)關(guān)系的調(diào)用圖 Main( ) ________________________________ CreatGraph() MiniSpanTree( ) ________________ Sort ( ) Find( ) Swapn( ) 1 由于對函數(shù)調(diào)用關(guān)系不是非常清楚，導(dǎo)致在程序設(shè)計(jì)的時(shí)候思路不是非常的清晰 2 該程序只能滿足圖頂點(diǎn)比較少的最小生成樹的實(shí)現(xiàn)，如果 用戶要求更大的空間，可以在創(chuàng)建圖的時(shí)候開辟更大的空間。 3 在程序輸入的時(shí)候，必須頂點(diǎn)數(shù)值小 的先輸入，否則程序?qū)?huì)出錯(cuò)。這也是程序應(yīng)該改進(jìn)的地方。 4 算法的時(shí)空分析 1，對矩陣的初始化 ，設(shè)輸入一個(gè) n個(gè)頂點(diǎn)的圖，那個(gè)將要對矩陣的 nxn 個(gè)元素進(jìn)行初始化，所以時(shí)間復(fù)雜度為 O(N2) 2,輸入權(quán)值和 邊的時(shí)間復(fù)雜度為 O(n),所以構(gòu)建圖的時(shí)間復(fù)雜度為 O(N2+N) O(N2) ?？臻g復(fù)雜度為 S（ N2） 4 在求最小生成樹函數(shù)中，對邊進(jìn)行標(biāo)記的時(shí)間復(fù)雜度為 O(N2)。對權(quán)值進(jìn)行排序的時(shí)間復(fù)雜度為 O(N2)，對 parent 數(shù)組賦值的時(shí)間復(fù)雜度為 o(n),所以該函數(shù)的時(shí)間復(fù)雜度為 O（ 2N2+N） 5 過這次課程設(shè)計(jì)，一方面 我 加深對課內(nèi)所學(xué)的有關(guān)數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計(jì)和時(shí)空分析等課程基本內(nèi)容的理解，另一方面，使我在 序設(shè)計(jì)方法（如抽象數(shù)據(jù)類型、結(jié)構(gòu)化分析、模塊化設(shè)計(jì)和結(jié)構(gòu)化設(shè)計(jì)）、 C 語言程序調(diào)試和 測試方面受到比較系統(tǒng)的嚴(yán)格的訓(xùn)練。 1,輸入圖的頂點(diǎn)數(shù)和變數(shù) 2 任意輸入兩個(gè)圖中連接的頂點(diǎn) 3 輸入這兩個(gè)頂點(diǎn)的
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1