應用C說話完成最小生成樹求解的簡略辦法。本站提示廣大學習愛好者：（應用C說話完成最小生成樹求解的簡略辦法）文章只能為提供參考，不一定能成為您想要的結果。以下是應用C說話完成最小生成樹求解的簡略辦法正文
最小生成樹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++; //掃描下一條邊
}
}
