kruskal_normal.cpp

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

#include "mst.h"
#include <vector>

edge_t	edge_normal[maxm], temp[maxm];
vector<int> adj[maxn];
bool	visit[maxn];

bool	dfs(int a, int b)
{
	int	i;
	if (a == b) return true;
	visit[a] = true;
	for (i = 0; i < adj[a].size(); i++)
		if (!visit[adj[a][i]])
			if (dfs(adj[a][i], b)) return true;
	return false;
}

bool	connect(int a, int b)
{
	memset(visit, 0, sizeof(visit));
	return dfs(a, b);
}

int		cmp(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_normal_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_normal[i].a, &edge_normal[i].b, &edge_normal[i].len);
	memcpy(temp, edge_normal, sizeof(edge_normal));

	fclose(stdin);
}

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

	memcpy(edge_normal, temp, sizeof(temp));
	qsort(edge_normal, m, sizeof(edge_t), cmp);

	sum = total = 0;
	for (i = 0; i < n; i++) adj[i].clear();

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