986
最小生成樹算法
#include <stdio.h>
#include <string.h>
#define INFINITY 1000000 // 無窮大
#define MAX_VERTEX_COUNT 6 // 圖最多頂點數
// 圖的鄰接矩陣
typedef int Graph[MAX_VERTEX_COUNT][MAX_VERTEX_COUNT];
/************************************************************************/
/* 功能：用Prim算法實現構造最小生成樹
/* 參數：g--圖
/* vertexCount -- 圖的頂點數
/* father -- 記錄頂點的雙親
/************************************************************************/
void Prim(Graph g, int vertexCount, int father[])
{
int i, j, k;
int lowCost[MAX_VERTEX_COUNT]; // 記錄從U到V－U具有最小代價的邊
int closeSet[MAX_VERTEX_COUNT];// 記錄了該邊依附的在U中的頂點,v屬於V-U
int used[MAX_VERTEX_COUNT]; // 記錄頂點是否已經被選中放入到U集合中
int min;
// 這裏初始選中頂點為1號頂點，這是可以修改的，本程序以1號頂點為默認
for (i = 0; i < vertexCount; i++)
{
// 最短距離初始化為其他節點到1號節點的距離
lowCost[i] = g[0][i];
// 標記所有節點的依附點皆為默認的1號節點
closeSet[i] = 0;
// 所有頂點均未被選中到U集合中
used[i] = 0;
// U集合中還沒有頂點，所有值設為-1，表示無雙親
father[i] = -1;
}
used[0] = 1; // 1號頂點選中，並加入到集合U中
// 依次選取剩餘頂點加入到集合中
for (i = 1; i < vertexCount; i++)
{
j = 0;
min = INFINITY;
// 找滿足條件的最小權值邊的頂點k及其編號
for (k = 1; k < vertexCount; k++)
{
// 邊權值較小且不在生成樹中
if (!used[k] && lowCost[k] < min)
{
min = lowCost[k]; // 選中頂點
j = k;
}
}
father[j] = closeSet[j]; // 記錄j號頂點的雙親
used[j] = 1; // 將j號頂點選入到生成樹中
// 打印邊即打印該邊連接的兩個頂點（權值最小）
printf("%d %d\n",j + 1,closeSet[j] + 1);
for (k = 1; k < vertexCount; k++)
{
// 繼續找邊權值更小的頂點
if (!used[k] && g[j][k] < lowCost[k])
{
lowCost[k] = g[j][k]; // 更新最小權值
closeSet[k] = j; // 記錄新的依附點
}
}
}
}
int main()
{
int i, j, weight;
Graph g;
int father[MAX_VERTEX_COUNT];
int vertexCount;
for (i = 0; i < MAX_VERTEX_COUNT; i++)
{
for (j = 0; j < MAX_VERTEX_COUNT; j++)
{
g[i][j] = INFINITY;
}
}
// 構造圖
while (scanf("%d%d%d", &i, &j, &weight) != EOF)
{
// 無向圖是對稱的
g[i - 1][j - 1] = weight;
g[j - 1][i - 1] = weight;
}
Prim(g, 6, father);
return 0;
}
最後更新：2017-04-03 18:52:05