prim_heap.cpp

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

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

struct e_t {
	int	next, len;	
};

vector <e_t> e[maxn];
int		p[maxn], d[maxn], heap[maxn], which[maxn];
int		heap_size = 0;

void	swap(int &a, int &b)
{
	int t;
	t = a; a = b; b = t;
}

void	heap_up(int k)
{
	while (k != 1 && d[heap[k]] < d[heap[k/2]]) {
		swap(heap[k], heap[k/2]);
		swap(which[heap[k]], which[heap[k/2]]);
		k = k/2;
	}
}

void	heap_down(int k)
{
	int	t, min;
	while (k < heap_size) {
		min = d[heap[k]]; t = k;
		if (k*2 <= heap_size && d[heap[k*2]] < min) {
			min = d[heap[k*2]]; t = k*2;
		}
		if (k*2+1 <= heap_size && d[heap[k*2+1]] < min) {
			min = d[heap[k*2+1]]; t = k*2 +1;
		}
		if (t == k) break;
		swap(heap[k], heap[t]);
		swap(which[heap[k]], which[heap[t]]);
		k = t;
	}
}

void	heap_adjust(int k)
{
	if (k != 1 && d[heap[k]] < d[heap[k/2]])
		heap_up(k);
	else
	if (k == 1 || d[heap[k]] > d[heap[k/2]])
		heap_down(k);
}

void	heap_insert(int k)
{
	heap_size ++;
	heap[heap_size] = k; which[k] = heap_size;
	heap_up(heap_size);
}

void	heap_delete(int k)
{
	heap[k] = heap[heap_size];
	which[heap[heap_size]] = k;
	heap_adjust(k);
	heap_size--;
}

int		prim_heap(int &n, int &m)
{
	int	sum = 0, i, k, min, total = 0;

	memset(p, 0, sizeof(p));
	memset(d, -1, sizeof(d));
	memset(which, 0, sizeof(which));
	d[0] = 0;
	heap_insert(0);
	
	while (1) {
		if (heap_size == 0) break;
		k = heap[1];
		sum += d[k]; p[k] = 1; heap_delete(1);
		total++;
		for (i = 0; i < e[k].size(); i++)
		if (p[e[k][i].next] == 0) {
			if (d[e[k][i].next] == -1) {
				d[e[k][i].next] = e[k][i].len;
				heap_insert(e[k][i].next);
			}
			else
			if (d[e[k][i].next] > e[k][i].len) {
				d[e[k][i].next] = e[k][i].len;
				heap_up(which[e[k][i].next]);
			}
		}
	}

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

void	prim_heap_read(int &n, int &m)
{
	int	i,a,b;
	e_t p;

	freopen(inputfilename, "r", stdin);
	
	scanf("%d %d", &n, &m);

	for (i = 0; i < n; i++) e[i].clear();
	for (i = 0; i < m; i++) {
		scanf("%d %d %d", &a, &b, &p.len);
		p.next = b; e[a].push_back(p);
		p.next = a; e[b].push_back(p);
	}

	fclose(stdin);
}