kruskal_disjoint_set.cpp

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

#include "mst.h"

int		father[maxn];
edge_t	edge[maxm], temp_edge[maxm];

int		root(int k)
{
	if (father[k] == k) return k;
	else {
		father[k] = root(father[k]);
		return father[k];
	}
}

bool	same(int a, int b)
{
	return root(a) == root(b);
}

void	merge(int a, int b)
{
	father[root(a)] = root(b);
}

int		cmp_len(const void *a, const void *b) {
	edge_t x = *(edge_t *) a;
	edge_t y = *(edge_t *) b;
	
	return (x.len-y.len);
}

void	kruskal_disjoint_set_read(int &n, int &m)
{
	int	i;

	freopen(inputfilename, "r", stdin);

	scanf("%d %d", &n, &m);
	for (i = 0; i < m; i++)
		scanf("%d %d %d", &edge[i].a, &edge[i].b, &edge[i].len);
	
	memcpy(temp_edge, edge, sizeof(edge));

	fclose(stdin);
}

int		kruskal_disjoint_set(int &n, int &m)
{
	int	i, sum, total;

	memcpy(edge, temp_edge, sizeof(temp_edge));
	qsort(edge, m, sizeof(edge_t), cmp_len);
	for (i = 0; i < n; i++) father[i] = i;

	sum = total = 0;
	for (i = 0; i < m; i++) {
		if (!same(edge[i].a, edge[i].b)) {
			sum += edge[i].len;
			merge(edge[i].a, edge[i].b);
			total ++;
		}
	}
	
	if (total == n-1)
		return sum;
	else
		return -1;
}