prim_normal.cpp

最小生成树 MST的四种算法实现。 包括普通的Kruskal算法和Prim算法

#include "mst.h"

int		matrix[maxn][maxn];
int		dist[maxn];
int		signal[maxn];

int		prim_normal(int &n, int &m)
{
	int	sum = 0, i, k, min, edge = 0;

	memset(signal, 0, sizeof(signal));
	memset(dist, -1, sizeof(dist));
	dist[0] = 0;
	while (1) {
		min = oo; k = -1;
		for (i = 0; i < n; i++)
			if (signal[i] == 0 && dist[i]!=-1 && dist[i] < min) {
				min = dist[i]; k = i;
			}
		if (k == -1) break;
		signal[k] = 1; sum += min; edge++;
		for (i = 0; i < n; i++)
			if (signal[i] == 0 && matrix[k][i] != -1 && (dist[i] == -1 || dist[i] > matrix[k][i]))
				dist[i] = matrix[k][i];
	}

	if (edge == n)
		return sum;
	else
		return -1;
}

void	prim_normal_read(int &n, int &m)
{
	int	i,a,b,c;

	freopen(inputfilename, "r", stdin);

	memset(matrix, -1, sizeof(matrix));
	scanf("%d %d", &n, &m);
	for (i = 0; i < m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		matrix[a][b] = c;
		matrix[b][a] = c;
	}

	fclose(stdin);
}