基于c語(yǔ)言的最小生成樹(shù)kruskal算法問(wèn)題-文庫(kù)吧資料
2024-11-16 06:26本頁(yè)面
【正文】 /頭頂點(diǎn) int end。對(duì)權(quán)值進(jìn)行排序的時(shí)間復(fù)雜度為 O(N2)，對(duì) parent 數(shù)組賦值的時(shí)間復(fù)雜度為 o(n),所以該函數(shù)的時(shí)間復(fù)雜度為 O（ 2N2+N） 5 過(guò)這次課程設(shè)計(jì)，一方面 我 加深對(duì)課內(nèi)所學(xué)的有關(guān)數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計(jì)和時(shí)空分析等課程基本內(nèi)容的理解，另一方面，使我在 序設(shè)計(jì)方法（如抽象數(shù)據(jù)類(lèi)型、結(jié)構(gòu)化分析、模塊化設(shè)計(jì)和結(jié)構(gòu)化設(shè)計(jì)）、 C 語(yǔ)言程序調(diào)試和 測(cè)試方面受到比較系統(tǒng)的嚴(yán)格的訓(xùn)練。 4 算法的時(shí)空分析 1，對(duì)矩陣的初始化 ，設(shè)輸入一個(gè) n個(gè)頂點(diǎn)的圖，那個(gè)將要對(duì)矩陣的 nxn 個(gè)元素進(jìn)行初始化，所以時(shí)間復(fù)雜度為 O(N2) 2,輸入權(quán)值和 邊的時(shí)間復(fù)雜度為 O(n),所以構(gòu)建圖的時(shí)間復(fù)雜度為 O(N2+N) O(N2) 。 3 在程序輸入的時(shí)候，必須頂點(diǎn)數(shù)值小 的先輸入，否則程序?qū)?huì)出錯(cuò)。 return 0。 MiniSpanTree(G)。 exit(1)。 G = (MGraph*)malloc(sizeof(MGraph))。 } return f。 printf( %d, %d %d\n, edges[i].begin, edges[i].end, edges[i].weight)。 m = Find(parent, edges[i].end)。 i = Garum。 以上是對(duì)權(quán)值進(jìn)行排序，排序之后將有利于回路的判斷，從而求出最小生成樹(shù) printf(最小生成樹(shù)為 :\n)。//sort 函數(shù)調(diào)用，對(duì)權(quán)值進(jìn)行排序 void sort(edge edges[],MGraph *G)//對(duì)權(quán)值進(jìn)行排序 void Swapn(edge *edges,int i, int j)//交換權(quán)值 以及頭和尾 在對(duì)權(quán)值排序時(shí)，若 (edges[i].weight edges[j].weigh)調(diào)用函數(shù) swapn 交換這兩條邊的權(quán)值以及頭和尾頂點(diǎn) 輸出鄰接矩陣 printf(請(qǐng)輸入 %d 與 %d 之間的權(quán)值 :\n, n, m)。 i++)//輸入邊和權(quán)值 Garc[n][m].adj = Garc[m][n].adj = 1。//先把矩陣中所有元素賦值為 0 for ( i = 1。//權(quán)值、頭頂點(diǎn)、尾頂點(diǎn)交換 void CreatGraph(MGraph *G)//構(gòu)件圖 { printf(請(qǐng)輸入邊數(shù)和頂點(diǎn)數(shù) :\n)。 //生成最小樹(shù) 函數(shù)的申明 int Find(int *, int )。 //圖構(gòu)建 函數(shù)申明 void sort(edge* ,MGraph *)。 typedef struct//用結(jié)構(gòu)體定義一個(gè)圖 { }MGraph。 3 序模塊之間的層次（調(diào)用）關(guān)系 主函數(shù)模塊 圖構(gòu)建模塊 最小生成樹(shù)模塊 define M 20 define MAX 20 規(guī)定該程序所能創(chuàng)建圖的最大頂 點(diǎn)數(shù)為 20 個(gè)點(diǎn) typedef struct //用結(jié)構(gòu)體定義邊 { }edge。 求該圖的最小生成樹(shù) { 對(duì)權(quán)值進(jìn)行排序 輸出排序后的權(quán)值和頂點(diǎn) 對(duì)各邊依次進(jìn)行判斷，是否存在回路，如果沒(méi)有回路，則輸出這條邊，否則，則不輸出 } system(pause)。 } 如果這個(gè)圖不存在系統(tǒng)將會(huì)非正常結(jié)束 CreatGraph(G)。 為這個(gè)圖動(dòng)態(tài)分配存儲(chǔ)空間 if (G == NULL)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1