prim.cpp

使用贪心算法实现PRIM最小生成树算法.经典的算法题目.

/////////////////////////////////////////////////////////////////////
// Prim Algorithm 
// Date  : 2008.09.05 
// Author:Shigao Liao 
/////////////////////////////////////////////////////////////////////

#include <iostream>
#include <fstream>

#define MaxInt 10000


//////////////////////////////////////////////////////////////////////
// New1Darray
template <class type>
void New1Darray(int size,type* &memory)
{
	memory=new type [size];
	int i=0;
	for(i=0;i<size;i++)
		memory[i]=0;
}

//////////////////////////////////////////////////////////////////////
// Del1Darray
template <class type>
void Del1Darray(int size,type* &memory)
{
	delete [] memory;
	memory=NULL;
}

//////////////////////////////////////////////////////////////////////
// New2Darray
template <class type>
void New2Darray(int rows,int cols,type** &memory)
{
	int i=0;
	memory=new type* [rows];
	for(i=0;i<rows;i++)
		memory[i]=new type [cols];
	int j=0;
	for(i=0;i<rows;i++)
		for(j=0;j<cols;j++)
			memory[i][j]=0;
}

//////////////////////////////////////////////////////////////////////
// Del2Darray
template <class type>
void Del2Darray(int rows,int cols,type** &memory)
{
	int i=0;
	for(i=0;i<rows;i++)
	{
		delete [] memory[i];
		memory[i]=NULL;
	}
	delete [] memory;
	memory=NULL;
}

/////////////////////////////////////////////////////////////////////
// InitArray function 
template <class type>
void InitArray(type** &c)
{
   int n,v;
   std::ifstream fin;
   fin.open("input.txt");
   fin>>n>>v;
   int i,j;
   i=j=0;
   for(i=1;i<=n;i++)
	   for(j=1;j<=n;j++)
		   fin>>c[i][j];
	   
   fin.close();
}


/////////////////////////////////////////////////////////////////////
// Prim function 
template <class type>
void Prim(int n,int v,type** c)
{
	bool* s;
	int*  closest;
	type* lowcost;

	std::ofstream fout;
	fout.open("output.txt");
	fout.close();

	New1Darray(n+1,s);
    New1Darray(n+1,closest);
	New1Darray(n+1,lowcost);
   
	int i=0;
	for(i=1;i<=n;i++)
	{
	  lowcost[i]=c[v][i];
	  if( (lowcost[i]!=MaxInt) )
		   closest[i]=v;
	  else closest[i]=0;
	}

	s[v]=true;
	closest[v]=v;
	lowcost[v]=0;



	for(i=1;i<n;i++)
	{

		int j=0;
		int u=i;
        
		// find the minial lowcost 
		type mintemp=MaxInt;
		for(j=1;j<=n;j++)
		{
		    if( (!s[j]) && (mintemp>lowcost[j]) )
			{
			   u=j;
			   mintemp=lowcost[j];
			}
		}
	    s[u]=true;
		std::ofstream fout;
		fout.open("output.txt",std::ios::app);
		fout<<closest[u]<<"--->"<<u<<"\n";
		fout.close();
        
		// Revise lowcost array 
		for(j=1;j<=n;j++)
		{   
			if(!s[j])
			{
				if( (c[u][j]<lowcost[j]))
				{
					lowcost[j]=c[u][j];
					closest[j]=u;
				}
			}
		}
	}

    
	Del1Darray(n+1,s);
	Del1Darray(n+1,closest);
	Del1Darray(n+1,lowcost);
}


/////////////////////////////////////////////////////////////////////
// main function 
int main()
{
    int n,v;
    int **c;
	std::ifstream fin;
	fin.open("input.txt");
	fin>>n>>v;
	New2Darray(n+1,n+1,c);
    InitArray(c);
    Prim(n,v,c);

    Del2Darray(n+1,n+1,c);
	fin.close();
	return 0;
}
/////////////////////////////////////////////////////////////////////