基于c語(yǔ)言的最小生成樹(shù)kruskal算法問(wèn)題-資料下載頁(yè)
2024-11-08 06:26本頁(yè)面
【導(dǎo)讀】舉例：若要在n個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需要架設(shè)n-1條線(xiàn)路即可。頂點(diǎn)，一個(gè)存儲(chǔ)邊，存儲(chǔ)邊的數(shù)組表明節(jié)點(diǎn)間的連通關(guān)系和邊的權(quán)值；利用克魯斯卡爾算法求網(wǎng)的最小生成樹(shù)；輸入的形式和輸入值的范圍：輸入的數(shù)值有各頂點(diǎn)，兩頂點(diǎn)之間的權(quán)值。頂點(diǎn)最多不能大于20個(gè)。操作結(jié)果;對(duì)edge進(jìn)行了排序。G->arc[i][j].adj=G->arc[j][i].adj=0;//先把矩陣中所有元素賦值為0
【正文】 e edges[],MGraph *G)//對(duì)權(quán)值進(jìn)行排序 { int i, j。 for ( i = 1。 i Garum。 i++) { for ( j = i + 1。 j = Garum。 j++) { if (edges[i].weight edges[j].weight) { Swapn(edges, i, j)。 } } } printf(權(quán)排序之后的為 :\n)。 for (i = 1。 i = Garum。 i++) { printf( %d, %d %d\n, edges[i].begin, edges[i].end, edges[i].weight)。 } } void Swapn(edge *edges,int i, int j)//交換權(quán)值 以及頭和尾 { int temp。 temp = edges[i].begin。 edges[i].begin = edges[j].begin。 edges[j].begin = temp。 temp = edges[i].end。 edges[i].end = edges[j].end。 edges[j].end = temp。 temp = edges[i].weight。 edges[i].weight = edges[j].weight。 edges[j].weight = temp。 } void MiniSpanTree(MGraph *G)//生成最小生成樹(shù) { int i, j, n, m。 int k = 1。 int parent[M]。 edge edges[M]。 for ( i = 1。 i Gvexnum。 i++) { for (j = i + 1。 j = Gvexnum。 j++) { if (Garc[i][j].adj == 1) { edges[k].begin = i。 edges[k].end = j。 edges[k].weight = Garc[i][j].weight。 k++。 } } } sort(edges, G)。 for (i = 1。 i = Garum。 i++) { parent[i] = 0。 } printf(最小生成樹(shù)為 :\n)。 for (i = 1。 i = Garum。 i++)//核心部分 { n = Find(parent, edges[i].begin)。 m = Find(parent, edges[i].end)。 if (n != m)//判斷是否有回路，如果有，舍棄 { parent[m] = n。 printf( %d, %d %d\n, edges[i].begin, edges[i].end, edges[i].weight)。 } } } int Find(int *parent, int f)//找尾 { while ( parent[f] 0) { f = parent[f]。 } return f。 } 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。 }
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1