Prim算法
#include "stdafx.h"
#include <iostream>
using namespace std;
#define MAX 1000
#define MAXCOST 0x3f3f3f3f
int graph[MAX][MAX];
int prim(int graph[][MAX], int n) //n顶点个数
{
int lowcost[MAX]; //lowcost[i]:以i为终点的边的最小权值,lowcost[i]=0表示i点加入了MST
int mst[MAX]; //mst[i]:对应lowcost[i]的起点,mst[i]=0表示起点i加入MST
int i, j, min, minid;
int max = 0;
for (i = 2; i <= n; i++)
{
lowcost[i] = graph[1][i]; //从1开始到所有点的权值
mst[i] = 1; //对应lowcost[i]的起点为1
}
mst[1] = 0; //1点在MST中
for (i = 2; i <= n; i++)
{
min = MAXCOST; //min为最小权值
minid = 0; //最小权值对应的点
for (j = 2; j <= n; j++)
{
if (lowcost[j] < min && lowcost[j] != 0)
{
min = lowcost[j];
minid = j;
}
}
//输出示例V1-V3=1
if (min > max)
max = min; //最小权值累加
lowcost[minid] = 0; //加入MST
for (j = 2; j <= n; j++) //更新lowcost[]和mst[]
{
if (graph[minid][j] < lowcost[j] && lowcost[j] != 0)
{
lowcost[j] = graph[minid][j];
mst[j] = minid;
}
}
}
return max;
}
int main()
{
int T;
int s;
int sum;
memset(graph, MAXCOST, sizeof(graph));
scanf("%d", &T);
while (T--)
{
scanf("%d", &s);
for (int i = 1; i < s + 1; i++)
for (int j = 1; j < s + 1; j++)
{
scanf("%d", &graph[i][j]);
if (!graph[i][j])
graph[i][j] = MAXCOST;
}
sum = prim(graph, s);
cout << sum << endl;
}
system("pause");
}