2.h

数据结构常用算法,prim算法.实现对于最近路径的选择,是常用的算法之一

#include"1.h"
#include"iostream.h"
#include"stdlib.h"
#include"fstream.h"
#define N 7
#define M 1000
class prim
{
	int a[N][N],mark[N],path[N];
	Queue Q;
	Queue P;
public:
	prim(char * file);
	void visite(int n);
	void display(int i);
};
prim::prim(char * file)
{
	ifstream fin;
	int i,j;
	fin.open(file,ios::in|ios::nocreate);
	if(!fin)
	{
		cerr<<"can't open";
		exit(1);
	}
	for(i=0;i<N;i++)
	{	for(j=0;j<N;j++)
		{	fin>>a[i][j];cout<<"  "<<a[i][j];}
	cout<<endl;
	}
		fin.close();
		for(i=1;i<N;i++)
		{	mark[i]=0;path[i]=0;}
}
void prim::visite(int n)
{
	int i;

	int l;
	int k;
	int court=1;

	if(court<N)
	{
                    
	mark[n]=1;
	for(i=2;i<N;i++)
		if(a[n][i]!=M&&mark[i]==0)
		{	
			Q.QInsert(i);
			P.QInsert(a[n][i]);
		}
		Q.bian_li();
		P.bian_li();
		k=P.find_min();
		cout<<"k"<<k<<endl;
		l=Q.Qvizite(k);
		cout<<"l"<<l<<endl;
		path[l]=n;
		n=l;
		court++; 
		visite(n);
	}
}
void prim::display(int i)
{
	if(i<N)
	{
		cout<<i<<"->"<<path[i]<<endl;
		i++;
		display(i);
	}
}