graph.h

自己在以前学数据结构时用C++模板写的一些常用数据,都测试过

/////////////////////////// 
//    // 
//   图数据结构  graph.h  // 
//    // 
////////////////////////// 

/////////////用邻接表的存储结构来构造一个图/////////////

#include <stdlib.h>
#include<iostream.h> 
#include"queue.h" 
#include"stack.h"

template<class NameType,class DisType>class ALGraph; 
template<class NameType,class DisType> struct Node    
{ 
	friend class ALGraph<NameType,DisType>; 
	int num; 
	DisType val; 
	Node<NameType,DisType> *next; 
}; 

template<class NameType,class DisType> struct GpNode //定义图的结点的类
{ 
	friend class ALGraph<NameType,DisType>; 
	NameType data;		//结点的数据的类型
	Node<NameType,DisType> *link; 
}; 

template<class NameType,class DisType> 
class ALGraph 
{ 
public: 
	void Creat();  //创建图 
	void PrintNode();    //打印图中的各个数据项 
	void DFS();    //图的深度优先搜索,主过程 
	void DFS(int v,int visited[]); // 子过程 
	void BFS();  //图的广度优先搜索，主过程 
	void BFS(int v,int visited[]); //子过程 
	void ShortPath();     //求最短路径
	//GpNode<NameType,DisType> *GetFirstVertex(int n);

private: 
	GpNode<NameType,DisType> *table; 
	Node<NameType,DisType> *p; 
	int NumNode;        //节点个数 
}; 

template<class NameType,class DisType> 
void ALGraph<NameType,DisType>::Creat() 
{ 
	do 
	{ 
		cout<<"请输入节点个数:  "; 
		cin >> NumNode; 
	}while(NumNode<=0); 
	table=new GpNode<NameType,DisType>[NumNode]; 
	cout<<"请输入各节点数据项"<<endl; 
	for(int i=0;i<NumNode;i++) 
	{ 
		cin>>table[i].data; 
		table[i].link=NULL; 
	} 
	cout<<"请输入各边的关系 (如: A B)"<<endl; 
	i=1; 
	NameType nodeA,nodeB; 
	bool findA,findB; 
	char ISExit; 
	int m,n; 
	do 
	{ 
		findA=findB=false; 
		cout<<"请输入第"<<i<<"对边的关系"<<endl; 
		cin>>nodeA>>nodeB; 
		for(m=0,n=0;m<NumNode&&n<NumNode&&!(findA & findB);) //查找边的节点 
		{ 
			if(nodeA!=table[m].data) 
				m++; 
			else 
				findA=true; 
			if(nodeB!=table[n].data) 
				n++; 
			else 
				findB=true; 

		} 
		if(!(findA & findB)) 
			cout<<"输入的节点数据项有错误"<<endl; 
		else				//从表前插入结点
		{ 
			p=new Node<NameType,DisType>; 
			p->next=table[m].link; 
			p->num=n; 
			table[m].link=p; 
			cout<<"请输入该对边的权值: "; 
			cin>>p->val; 
			i++; 
		} 
		cout<<"是否继续输入: y)继续,X)任意键退出 "; 
		cin>>ISExit; 
		if(ISExit!='y'&&ISExit!='Y') 
		break; 
	}while(true);  
} 

template<class NameType,class DisType> 
void ALGraph<NameType,DisType>::PrintNode() 
{ 
	cout<<"图中各节点数据项 : "; 
	for(int i=0;i<NumNode;i++) 
		cout<<table[i].data<<" "; 
	cout<<endl; 
} 

template<class NameType,class DisType> 
void ALGraph<NameType,DisType>::DFS() 
{ 
	int *visited=new int[NumNode]; 
	cout<<"图的深度优先搜索 : "; 
	for(int i=0;i<NumNode;i++) 
		visited[i]=0; 
	for(i=1;i<NumNode;i++) //遍历孤立节点 
		DFS(i,visited); 
	delete []visited; 
	cout<<endl; 
} 

template<class NameType,class DisType> 
void ALGraph<NameType,DisType>::DFS(int v,int visited[]) 
{ 
	Node<NameType,DisType> *t; 
	if(visited[v]==0) 
		cout<<table[v].data<<" "; 
	visited[v]=1; 
	t=table[v].link; 
	while(t!=NULL) 
	{ 
		if(visited[t->num]==0) 
		DFS(t->num,visited); 
		t=t->next; 
	} 
} 

template<class NameType,class DisType> 
void ALGraph<NameType,DisType>::BFS() 
{ 
	int *visited=new int[NumNode]; 
	cout<<"图的广度优先搜索 : "; 
	for(int i=0;i<NumNode;i++) 
	visited[i]=0; 
	for( i=0;i<NumNode;i++) 
		BFS(i,visited); 
} 

template<class NameType,class DisType> 
void ALGraph<NameType,DisType>::BFS(int v,int visited[]) 
{ 
	Queue<int> q; 
	int n; 
	if(visited[v]==0) 
	{ 
		visited[v]=1; 
		cout<<table[v].data<<" "; 
		q.EnQueue(v); 
		while(!q.ISEmpty()) 
		{ 
			n=q.DelQueue(); 
			p=table[n].link; 
			while(p!=NULL) 
			{ 
				n=p->num; 
				if(visited[n]==0) 
				{ 
					cout<<table[n].data<<" "; 
					visited[n]=1; 
				} 
				p=p->next; 
			} 
		} 
	} 
} 

template<class NameType,class DisType>
void ALGraph<NameType,DisType>::ShortPath()
{
	
}


////////////////定义最小生成树的结点类//////////////////////////
template <class Type>
class TreeNode
{
	public:
		Type vertex;
		float weight;
};

//////////////用邻接矩阵的存储结构为来定义图////////////////////
const int MaxWeight=10000;
const int MaxEdges=50;
const int MaxVertices=10;
template <class Type>
class MGraph
{
	public:
		MGraph();
		void CreatGraph();
		bool GraphEmpty()const{return numberVertices==0||numberEdges==0;}
		bool GraphFull()const{return numberVertices==MaxVertices||numberEdges==MaxEdges;}
		int	NumberOfVertices(){return numberVertices;}//返回当前顶点的个数
		Type GetValue(int i){return i>=0&&i<=numberVertices?verticesList[i]:NULL;}//取顶点i的值
		float GetWeight(int u,int v);//求顶点v,u边上的权值
		int GetFirstNeighbor(int v);//求v的第一个邻接顶点
		int GetNextNeighbor(int v,int w);//求v的邻接点W的下一个邻接顶点
		void InsertVertex(const Type vertex);//插入一个顶点
		void InsertEdge(int u,int v,int weight);//插入一条边
		void RemoveVetex(int v);//删除V和所有和它有关的边
		void RemoveEdge(int u,int v);//删除(u,v)边
		void DFS();//深度优先
		void DFS(int v,int visit[]);//子程序
		void BFS();//广度优先
		void BFS(int v,int visit[]);//子程序
		void PrimeMinTree();//普里母算法生成图中最小生成树
		void KruskalMinTree(Type vertex);//克鲁思卡算法生成图中最小生成树
		void ShortPath(Type vertex);//找出最短路线
		void TopologicalOrder();
	private:
		Type verticesList[MaxVertices];//用来存储图的结点
		float Edge[MaxVertices][MaxVertices];//用来存储图中各边的权值
		int numberEdges;//记录当前边的条数
		int numberVertices;//记录当前结点的个数
		int GetVertexPos(const Type vertex);//获得当前结点的位置
		TreeNode<Type> *minTree;//记录最小生成树
		float *smallestWeight;//记录开始结点到各结点的最小路线的权值
		void FindInDegree(int *&indegree);
		void ChangeDegree(int *&indegree,int node);
		int NumberOfArray(int *a);//得到数组中元素的个数
}; 

template <class Type>
void MGraph<Type>::CreatGraph()
{
	do 
	{ 
		cout<<"请输入节点个数:  "; 
		cin >>numberVertices; 
	}while(numberVertices<0); 
	cout<<"请输入各节点数据项"<<endl; 
	for(int i=0;i<numberVertices;i++) 
		cin>>verticesList[i]; 
	cout<<"请输入各边的关系 (如: A B)"<<endl; 
	i=1; 
	Type nodeA,nodeB; 
	float weight;
	bool findA,findB; 
	char ISExit; 
	int m,n; 
	do 
	{ 
		findA=findB=false; 
		cout<<"请输入第"<<i++<<"对边的关系及权值"<<endl; 
		cin>>nodeA>>nodeB>>weight; 
		for(m=0,n=0;m<numberVertices&&n<numberVertices&&!(findA & findB);) //查找边的节点 
		{ 
			if(nodeA!=verticesList[m]) 
				m++; 
			else 
				findA=true; 
			if(nodeB!=verticesList[n]) 
				n++; 
			else 
				findB=true; 
		} 
		if(!(findA&&findB)) 
			cerr<<"输入的节点数据项有错误!!!!!"<<endl; 
		else
			Edge[m][n]=weight;
		cout<<"是否继续输入: y)继续,X)任意键退出 "; 
		cin>>ISExit; 
		if(ISExit!='y'&&ISExit!='Y') 
			break; 
	}while(true);  	
}

template <class Type>
float MGraph<Type>::GetWeight(int u,int v)
{
	if(v!=-1&&u!=-1)
		return Edge[u][v];
	else
		return 0;
}

template <class Type>
int MGraph<Type>::GetVertexPos(const Type vertex)
{
	for(int i=0;i<numberVertices;i++)
		if(verticesList[i]==vertex)return i;
	return -1;
}

template <class Type>
MGraph<Type>::MGraph()
{
	for(int i=0;i<MaxVertices;i++)
		for(int j=0;j<MaxVertices;j++)
			if(i==j)
				Edge[i][j]=0;
			else
				Edge[i][j]=MaxWeight;
	numberEdges=0;
	numberVertices=0;
}

template <class Type>
int MGraph<Type>::GetFirstNeighbor(const int v)
{
	if(v!=-1)
	{
		for(int j=0;j<numberVertices;j++)
			if(Edge[v][j]>0&&Edge[v][j]<MaxWeight)
				return j;
	}
	return -1;
}

template <class Type>
int MGraph<Type>::GetNextNeighbor(int v,int w)
{
	if(v!=-1&&w!=-1)
	{
		for(int j=w+1;j<numberVertices;j++)
			if(Edge[v][j]>0&&Edge[v][j]<MaxWeight)
				return j;
	}
	return -1;
}

template <class Type>
void MGraph<Type>::InsertVertex(const Type vertex)//插入一个结点值为vertex的结点
{
	if(GraphFull())
	{
		cerr<<"the graph is full"<<endl;
		return false;