# 普里姆算法求最小生成树

ngmm 15 2015-06-07 22:56 0

### 基本信息

× 1

```    #include "iostream"
using namespace std;

const int num = 9; //节点个数
#define Infinity 65535;
//本例中以节点0作为生成树的起始节点
void MinSpanTree_Prime(int graphic[num][num]){
int lowcost[num]; //记录从节点num到生成树的最短距离，如果为0则表示该节点已在生成树中
int sum = 0; // 记录最小生成树边权重之和
//选取0节点作为生成树的起点
for (int i = 0; i < num; i++)
lowcost[i] = graphic[0][i];

for (int i = 1; i < num; i++){
int min = Infinity;
int index;
for (int j = 1; j < num; j++){
if (lowcost[j] != 0 && lowcost[j] < min){
index = j;
min = lowcost[j];
}
}
sum += min;
lowcost[index] = 0; //将当前节点放入生成树中
cout << adjvex[index] << " -> " << index << endl;
//修正其他节点到生成树的最短距离
for (int j = 1; j < num; j++){
if (lowcost[j] != 0 && graphic[index][j] < lowcost[j]){
lowcost[j] = graphic[index][j];
}
}
}
cout << "sum = " << sum << endl;
}

int main(){
int graphic[num][num];
for (int i = 0; i < num; i++)
for (int j = 0; j < num; j++){
if (i == j)
graphic[i][j] = 0;
else
graphic[i][j] = Infinity;
}
graphic[0][1] = 1;
graphic[0][2] = 5;
graphic[1][0] = 1;
graphic[1][2] = 3;
graphic[1][3] = 7;
graphic[1][4] = 5;
graphic[2][0] = 5;
graphic[2][1] = 3;
graphic[2][4] = 1;
graphic[2][5] = 7;
graphic[3][1] = 7;
graphic[3][4] = 2;
graphic[3][6] = 3;
graphic[4][1] = 5;
graphic[4][2] = 1;
graphic[4][3] = 2;
graphic[4][5] = 3;
graphic[4][6] = 6;
graphic[4][7] = 9;
graphic[5][2] = 7;
graphic[5][4] = 3;
graphic[5][7] = 5;
graphic[6][3] = 3;
graphic[6][4] = 6;
graphic[6][7] = 2;
graphic[6][8] = 7;
graphic[7][4] = 9;
graphic[7][5] = 5;
graphic[7][6] = 2;
graphic[7][8] = 4;
graphic[8][6] = 7;
graphic[8][7] = 4;

MinSpanTree_Prime(graphic);

return 0;
}  ```