最小生成樹Prim算法樸素版
有幾點需要說明一下。
1、2個for循環都是從2開始的，因為一般我們默認開始就把第一個節點加入生成樹，因此之后不需要再次尋找它。
2、lowcost[i]記錄的是以節點i為終點的最小邊權值。初始化時因為默認把第一個節點加入生成樹，因此lowcost[i] = graph[1][i]，即最小邊權值就是各節點到1號節點的邊權值。
3、mst[i]記錄的是lowcost[i]對應的起點，這樣有起點，有終點，即可唯一確定一條邊了。初始化時mst[i] = 1，即每條邊都是從1號節點出發。
編寫程序:對于如下一個帶權無向圖，給出節點個數以及所有邊權值，用Prim算法求最小生成樹。
輸入數據:
7 11
A B 7
A D 5
B C 8
B D 9
B E 7
C E 5
D E 15
D F 6
E F 8
E G 9
F G 11
輸出:
A - D : 5
D - F : 6
A - B : 7
B - E : 7
E - C : 5
E - G : 9
Total:39
最小生成樹Prim算法樸素版 C語言實現 代碼如下
#include <stdio.h>#include <stdlib.h> #define MAX 100#define MAXCOST 0x7fffffff int graph[MAX][MAX]; int Prim(int graph[][MAX], int n){ /* lowcost[i]記錄以i為終點的邊的最小權值，當lowcost[i]=0時表示終點i加入生成樹 */ int lowcost[MAX]; /* mst[i]記錄對應lowcost[i]的起點，當mst[i]=0時表示起點i加入生成樹 */ int mst[MAX]; int i, j, min, minid, sum = 0; /* 默認選擇1號節點加入生成樹，從2號節點開始初始化 */ for (i = 2; i <= n; i++) { /* 最短距離初始化為其他節點到1號節點的距離 */ lowcost[i] = graph[1][i]; /* 標記所有節點的起點皆為默認的1號節點 */ mst[i] = 1; } /* 標記1號節點加入生成樹 */ mst[1] = 0; /* n個節點至少需要n-1條邊構成最小生成樹 */ for (i = 2; i <= n; i++) { min = MAXCOST; minid = 0; /* 找滿足條件的最小權值邊的節點minid */ for (j = 2; j <= n; j++) { /* 邊權值較小且不在生成樹中 */ if (lowcost[j] < min && lowcost[j] != 0) { min = lowcost[j]; minid = j; } } /* 輸出生成樹邊的信息:起點，終點，權值 */ printf("%c - %c : %d/n", mst[minid] + 'A' - 1, minid + 'A' - 1, min); /* 累加權值 */ sum += min; /* 標記節點minid加入生成樹 */ lowcost[minid] = 0; /* 更新當前節點minid到其他節點的權值 */ for (j = 2; j <= n; j++) { /* 發現更小的權值 */ if (graph[minid][j] < lowcost[j]) { /* 更新權值信息 */ lowcost[j] = graph[minid][j]; /* 更新最小權值邊的起點 */ mst[j] = minid; } } } /* 返回最小權值和 */ return sum;} int main(){ int i, j, k, m, n; int x, y, cost; char chx, chy; /* 讀取節點和邊的數目 */ scanf("%d%d", &m, &n); getchar(); /* 初始化圖，所有節點間距離為無窮大 */ for (i = 1; i <= m; i++) { for (j = 1; j <= m; j++) { graph[i][j] = MAXCOST; } } /* 讀取邊信息 */ for (k = 0; k < n; k++) { scanf("%c %c %d", &chx, &chy, &cost); getchar(); i = chx - 'A' + 1; j = chy - 'A' + 1; graph[i][j] = cost; graph[j][i] = cost; } /* 求解最小生成樹 */ cost = Prim(graph, m); /* 輸出最小權值和 */ printf("Total:%d/n", cost); //system("pause"); return 0; }Kruskal算法：
void Kruskal(Edge E[],int n,int e){ int i,j,m1,m2,sn1,sn2,k; int vset[MAXE]; for (i=0;i<n;i++) vset[i]=i; //初始化輔助數組 k=1; //k表示當前構造最小生成樹的第幾條邊,初值為1 j=0; //E中邊的下標,初值為0 while (k<n) //生成的邊數小于n時循環 { m1=E[j].u;m2=E[j].v; //取一條邊的頭尾頂點 sn1=vset[m1];sn2=vset[m2]; //分別得到兩個頂點所屬的集合編號 if (sn1!=sn2) //兩頂點屬于不同的集合,該邊是最小生成樹的一條邊 { printf(" (%d,%d):%d/n",m1,m2,E[j].w); k++; //生成邊數增1 for (i=0;i<n;i++) //兩個集合統一編號 if (vset[i]==sn2) //集合編號為sn2的改為sn1 vset[i]=sn1; } j++; //掃描下一條邊 }}新聞熱點
疑難解答
圖片精選
