tree.cpp

根据kruskal算法写成的求一棵树的最小生成树的程序。

/**************************************************/
/*程序功能:生成最短树							  */
/*作者:hzj									  */
/*日期:2008.10.29								  */
/**************************************************/

#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

class Edge
{
public:
	int a, b, z;
};

int find(int x, vector<int> &node);
void unionSet(int r1, int r2, vector<int> &node);
void readData(vector<Edge> &edge, int &nNode, int &nEdge);		//读取数据
void sortData(vector<Edge> &edge, int &nEdge);					//对边权值排序,从大到小
void kruskal(vector<Edge> &edge, int &nNode, int &nEdge);

int main()
{

	int nNode, nEdge;
	vector<Edge> edge;
	readData(edge, nNode, nEdge);							//读取数据正确
	sortData(edge, nEdge);									//排序正确
	kruskal(edge, nNode, nEdge);

	return 0;
}

void readData(vector<Edge> &edge, int &nNode, int &nEdge)
{
	ifstream fin("tree.in");
	fin >> nNode >> nEdge;

	Edge temp;
	for (int i = 0; i < nEdge; i++)
	{
		fin >> temp.a >> temp.b >> temp.z;
		edge.push_back(temp);
	}
	fin.close();
}

void sortData(vector<Edge> &edge, int &nEdge)
{
	Edge temp;
	for (int i = 0; i < nEdge; i++)
	{
		for (int j = i; j < nEdge; j++)
		{
			if (edge[i].z < edge[j].z)
			{
				temp = edge[i];
				edge[i] = edge[j];
				edge[j] = temp;
			}
		}
	}
}

int find(int x, vector<int> &node)					// 查找根
{
	int i = x;
	int temp;
	if (node[x] != x) x = find(node[x], node);
	while (i != x)									//压缩路径
	{
		temp = node[i];
		node[i] = x;
		i = node[i];
	}

	return x;
}

void unionSet(int r1, int r2, vector<int> &node)			//合并r1和r2的根结点,以权值大的作为根结点
{
	int p1 = find(r1, node);
	int p2 = find(r2, node);
	if (p1 > p2) node[p2] = p1;
	else
		node[p1] = p2;
}
void kruskal(vector<Edge> &edge, int &nNode, int &nEdge)
{
	vector<int> node;
	for (int i = 0; i <= nNode; i++)			//初始化每个结点所在的集合
		node.push_back(i);

	vector<Edge> tree;							//tree代表生成的树
	Edge minZ;									//用于取最小的边
	unsigned int n = nEdge-1;

	minZ = edge[n--];
	tree.push_back(minZ);
	edge.pop_back();
	int minSum = minZ.z;
	unionSet(minZ.a, minZ.b, node);

	while (tree.size() < nNode-1 && !edge.empty())
	{
		minZ = edge[n--];
		edge.pop_back();
		if (find(minZ.a, node) != find(minZ.b, node))
		{
			minSum += minZ.z;
			tree.push_back(minZ);
			unionSet(minZ.a, minZ.b, node);
		}
	}

	ofstream fout("tree.out");

	fout << minSum << endl;
	for (int i = 0; i < tree.size(); i++)
		fout << tree[i].a << " " << tree[i].b << endl;

	fout.close();
}