# ifndef Graph_h

# include <iostream.h>
# include <stdlib.h>

# define MAXNUM 1000
# define MAXSIZE 100

template <class Type> struct Edgenode  //節(jié)點的定義
{
	int head;
	int tail;
	Type cost;
};

template <class Type> class Minspantree
{
	public:
		Minspantree(int sz=MAXSIZE);
		int Insert(Edgenode <Type> &e);
        Edgenode <Type>& Getvalue(int i) { return edgevalue[i];}
		friend ostream & operator << (ostream &out,Minspantree<Type> &T);
		int Getsize() {return Maxsize;}
	protected:
		int Maxsize;
		int current;
		Edgenode <Type> *edgevalue;
};

template <class Type> class Graph
{
	public:
		Graph(int sz1=Maxsize,int sz2=Maxsize);
		int Insert(Edgenode <Type> &e);
        Type Getedge (int i,int j) {return Edge[i][j];}
        friend ostream& operator <<(ostream &out,Graph <Type> &a);
		~Graph();
		void Shortestpath(int,int);
		int Choose(int,int,int);
		void Prim (Minspantree <Type> &T,int n);
	protected:
		int edgenum,vertnum;   //邊數(shù)和點數(shù)
		Type Edge[MAXSIZE][MAXSIZE];
		int *path;             //路徑數(shù)組
		Type *dist;
		int *S;
};

//最小生成樹的函數(shù)實現(xiàn)
template <class Type> Minspantree<Type>::Minspantree(int sz)
{
    current=0;
    Maxsize=sz;
	edgevalue=new Edgenode <Type> [sz];
}

template <class Type> int Minspantree <Type>::Insert(Edgenode <Type> &item)
{
	if(current>Maxsize-1) {cout<<"最小生成樹已經(jīng)滿，不能插入"<<endl;return 0;}
	else{
        edgevalue[current].head=item.head;
        edgevalue[current].tail=item.tail;
        edgevalue[current].cost=item.cost;
	    current++;
	    return 1;
	}
}

template <class Type> ostream & operator << (ostream &out,Minspantree <Type> &T)  //數(shù)組的輸出
{
	out<<"景點"<<T.Getvalue(0).head+1<<" -> "<<"景點"<<T.Getvalue(0).tail+1;
	for(int i=1;i<=T.Getsize()-1;i++) out<<" -> "<<"景點"<<T.Getvalue(i).tail+1;       
	out<<endl;
	return out;
}

//圖有關成員函數(shù)的實現(xiàn)

template <class Type> Graph <Type>::Graph(int sz1,int sz2)
{
	if(sz1==0||sz2==0) {cout<<"頂點和邊數(shù)不能為零!!"<<endl;exit(1);}
	else if(sz1>MAXSIZE) {cout<<"頂點不能超過1000"<<endl;exit(1);}
	else{
		edgenum=sz2;vertnum=sz1;		
		for(int i=0;i<sz1;i++)
			for(int j=0;j<sz1;j++)
			{
				if(i==j) Edge[i][j]=0;
				else Edge[i][j]=MAXNUM;
			}
		dist=new Type[sz1];
	    path=new int[sz1];
	    S=new int[sz1];
	}
}

template <class Type> int Graph <Type>::Insert(Edgenode <Type> &e)
{
	Edge[e.head-1][e.tail-1]=e.cost;
	Edge[e.tail-1][e.head-1]=e.cost;
	return 1;
}

template <class Type> ostream& operator <<(ostream &out,Graph <Type> &a)  //輸出整個圖
{
	for(int i=0;i<vertnum;i++)
		for(int j=0;j<vertnum;j++)
		{
			out<<i+1<<" "<<j+1<<" "<<Getedge(i,j)<<"   "<<endl;
		}
}

template <class Type> Graph<Type>::~Graph()   //析構輔助數(shù)組
{
	delete []path;
	delete []dist;
	delete []S;
}

//迪克斯特拉算法求shortestpath
template <class Type> void Graph<Type> ::Shortestpath ( int n, int v)
{
        for ( int i=0; i<n; i++) 
		{				
        dist[i] = Edge[v][i];     //dist和path數(shù)組初始化
        S[i] = 0;					
        if ( i != v && dist[i] < MAXNUM ) 	path[i] = v;		
        else path[i] = -1;				        
		}  
       S[v] = 1;  dist[v] = 0;	//頂點v加入頂點集合       
       for ( i = 0; i < n-1; i++ ) //選擇當前不在集合S中具有最短路徑的頂點u
	   {			
           Type min = MAXNUM;  
		   int u = v;
           for ( int j = 0; j < n; j++ )		
	           if ( !S[j] && dist[j] < min ) 
			   { 
				   u = j;   
				   min = dist[j]; 
			   }
          S[u] = 1;	                //將頂點u加入集合S,表示它已經(jīng)在最短路徑上
          for ( int w = 0; w < n; w++ )    //修改 
	       if ( !S[w] && Edge[u][w] < MAXNUM &&dist[u] + Edge[u][w] < dist[w] ) 
		   {
	       dist[w] = dist[u] + Edge[u][w]; 
	       path[w] = u;
		   }
	   }

}

template <class Type> int Graph <Type>::Choose(int n,int v,int t)
{
	Shortestpath(n,v-1);
	if(t!=0)                                //輸出任意兩個景點的長度
	{
           cout<<" 景點"<<v<<" -> 景點"<<t<<" 的最短路徑 : ";
           Type length=dist[t-1];
           int k=1,p=t-1;
           while(path[p]!=-1)				 //檢測最短路徑上的點個數(shù) 
		   {
				k++;
				p=path[p];
		   }
		   int m=k;
		   int *a=new int[m];                //創(chuàng)建輔助數(shù)組存儲景點
		   p=t-1;
		   a[k-1]=t-1;
		   while(path[p]!=-1)
		   {
				k--;
				a[k-1]=path[p];
				p=path[p];
		   }
		   for( int j=0;j<m-1;j++)
				cout<<"景點"<<a[j]+1<<" -> ";
		   cout<<"景點"<<a[j]+1<<" , ";
		   cout<<"路徑全長為"<<length<<endl;
		   return 1;
	   }
	else if(t==0)
	{
			for(int j=1;j<=vertnum;j++)
			{
				if(j!=v) Choose(n,v,j);
			}
			return 1;
	}
	return 0;
}

template <class Type> void Graph <Type>::Prim (Minspantree <Type> &T,int n)  //prim算法求最小生成樹
{
    int NumVertices = n;	 //圖中頂點數(shù)
    Type *lowcost = new Type[NumVertices];			
    int *nearvex = new int[NumVertices];			
    for ( int i = 1; i < NumVertices; i++ ) 
	{
        lowcost[i] = Edge[0][i]; //頂點0到各邊的代價
        nearvex[i] = 0;	         //及最短帶權路徑
	}
	nearvex[0] = -1;      //頂點0加到生成樹頂點集合
    int count = 1;          //生成樹邊值數(shù)組存放指針
    Edgenode <Type> e;    //最小生成樹結點輔助單元
    for ( i = 1; i < NumVertices; i++ ) 
	{   //循環(huán)n-1次, 加入n-1條邊			
       Type min = MAXNUM;  int v = 0;		
       for ( int j = 0; j < NumVertices; j++ )		
           if ( nearvex[j] != -1 && lowcost[j] < min )
		   { v = j;  min = lowcost[j]; }  //求生成樹外頂點到生成樹內(nèi)頂點具有最小   //權值的邊, v是當前具最小權值的邊的位置       
       if ( v ) 
	   {   //v==0表示再也找不到要求的頂點了  //向生成樹邊值數(shù)組內(nèi)存放                  
           if(count==1)
		   {  
			   e.head=0;
		       count++;
		   }
		   else
               e.head = nearvex[v];
		   e.tail = v;  
           e.cost = lowcost[v];   
           T.Insert (e);           //選出的邊加入生成樹
           nearvex[v] = -1;    //作該邊已加入生成樹標記
           for ( j = 1; j < NumVertices; j++ )
			   if ( nearvex[j] != -1 &&Edge[v][j]<lowcost[j])     //j不在生成樹中    //需要修改
			   {
				   lowcost[j] = Edge[v][j];
                   nearvex[j] = v;
			   }
      }
   }
}

# endif