数据结构与算法问题 sdut oj 2144 最小生成树

题目描述

输入

输出

示例输入

3 2
1 2 1
1 3 1

示例输出

2

#include <iostream>
using namespace std;
const int INTIFIY = 65535;
typedef struct graph
{
	int vex[200];
	int adj[200][200];
	int numvex, numedge;
}graph;

void create(graph * g)
{
	int w, j, i,k;
	cin >> g->numvex >> g->numedge;
	for ( i = 1; i<g->numedge; i++)
		for (j = 1; j<g->numedge; j++)
			g->adj[i][j] = INTIFIY;

	for (i = 1; i <= g->numvex; i++)
		g->vex[i] = i;
	for ( k = 0; k<g->numedge; k++)
	{
		cin >> i >> j >> w;
		g->adj[i][j] = w;
		g->adj[j][i] = g->adj[i][j];
	}
}

void prim(graph * g)
{

	int min, i, k, j, num = 0;
	int lowcost[200];
	int adj[200];
	lowcost[1] = 0; //存放权值
	adj[1] = 1; //每个结点的前驱
	for (i = 2; i<=g->numvex; i++)
	{
		lowcost[i] = g->adj[1][i];
		adj[i] = 0;
	}
	for (i = 2; i<=g->numvex; i++)
	{
		min = INTIFIY;
		j = 2;
		while (j<=g->numvex)
		{
			if (lowcost[j] != 0 && lowcost[j] < min)
			{
				min = lowcost[j];
				k = j;
			}
			j++;
			num += min;
		}
		lowcost[k] = 0;
		for (i = 2; i<=g->numvex; i++)
		{
			if (lowcost[i] != 0 && lowcost[i]>g->adj[k][i])
			{
				lowcost[i] = g->adj[k][i];
				adj[i] = k;
			}

		}

	}
	cout << num << endl;
}

int main()
{
	graph *g = new graph;
	create(g);
	prim(g);
	system("pause");
}

数据结构与算法问题 sdut oj 2144 最小生成树,布布扣,bubuko.com

数据结构与算法问题 sdut oj 2144 最小生成树

原文：http://blog.csdn.net/leviathan_/article/details/38561253