tree.cpp

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

/****************************************************************/
/*程序功能：生成最短树											*/
/*作者：何志杰													*/
/*学号:2007011303												*/
/*完成日期：2008.11.05											*/
/****************************************************************/

#include <fstream>
using namespace std;

void readData(int **&matrix, int &nNode, int &nEdge);	//读数据
void prim(int **&matrix, int &nNode, int &nEdge);

int main()
{
	int **matrix;									//权矩阵
	int nNode, nEdge;								//结点数和边数
	readData(matrix, nNode, nEdge);
	if (matrix)
	{
		prim(matrix, nNode, nEdge);

		for (int i = 0; i < nNode+1; i++)			//释放空间
			delete [] matrix[i];
		delete [] matrix;
	}

	return 0;
}

void readData(int **&matrix, int &nNode, int &nEdge)
{
	ifstream fin("tree.in");
	if (!fin) return;
	fin >> nNode >> nEdge;

	matrix = new int *[nNode+1];
	for (int i = 0; i <= nNode; i++)
		matrix[i] = new int[nNode+1];

	for (int i = 0; i <= nNode; i++)			//初始化
	{
		for (int j = 0; j <= nNode; j++)
		{
			matrix[i][j] = 150;
		}
	}

	int a, b, z;
	for (int i = 0; i < nEdge; i++)				//读入数据
	{
		fin >> a >> b >> z;
		matrix[a][b] = z;
		matrix[b][a] = z;
	}
}

void prim(int **&matrix, int &nNode, int &nEdge)
{
	typedef pair<int, int> Node;		
	Node *tree = new Node[nNode+1];				//生成的树
	int *a = new int[nNode+1];					//标记结点是否已经被选进树中
	for (int i = 0; i <= nNode; i++)			//0表示未选进
		a[i] = 0;

	a[1] = 1;
	int node = 1;
	int minSum = 0;
	while (node != nNode)
	{
		int minZ = 120;
		int minA, minB;

		for (int i = 1; i <= nNode; i++)
		{
			if (a[i] == 0)	continue;
			for (int j = 1; j <= nNode; j++)
			{
				if (a[j] == 1) continue;
				if (minZ > matrix[i][j])
				{
					minZ = matrix[i][j];
					minA = i;
					minB = j;
				}
			}
		}
		a[minB] = 1;
		minSum += matrix[minA][minB];
		tree[node].first = minA;
		tree[node].second = minB;
		node++;
	}
	
	ofstream fout("tree.out");

	fout << minSum << endl;
	for (int i = 1; i < nNode; i++)
	{
		fout << tree[i].first << " " << tree[i].second << endl;
	}
	
}