Prim算法学习

#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;
#define N 10005
#define INF 1000000000

int a[N][N];
bool vis[N];
int dis[N];
int ans;
int n;

bool Prim()
{
	memset(vis, 0, sizeof(vis));
	for (int i = 1; i <= n; i++)
	{
		dis[i] = INF;
	}
	ans = 0;
	dis[1] = 0;
	for (int i = 1; i <= n; i++)
	{
		int tmp = INF;
		int k = 0;
		for (int j = 1; j <= n; j++)
		{
			if (vis[j]) continue;
			if (tmp > dis[j])
			{
				tmp = dis[j];
				k = j;
			}
		}
		vis[k] = true;
		if (tmp == INF) return false;
		ans += tmp;
		for (int j = 1; j <= n; j++)
		{
			if (vis[j]) continue;
			if (dis[j] > a[k][j])
			{
				dis[j] = a[k][j];
			}
		}
	}
	return true;
}
int main()
{
	while (cin >> n)
	{
		if (n == -1) break;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
				cin >> a[i][j];
		}
		Prim();
		cout << ans << endl;
	}
	return 0;
}

Prim算法学习,布布扣,bubuko.com

Prim算法学习

原文：http://blog.csdn.net/dutsoft/article/details/23210597