2007327.cpp

带权有向以及无向图的各种操作

#include<iostream.h>
#include"2007327.h"
template<class vertexType,class arcType>
Graph<vertexType,arcType>::Graph(int num){
	for(int i=0;i<num;i++)
		for(int j=0;j<num;j++) Arcs[i][j]=0;
		CurrentNumArcs=0;
}
template<class vertexType,class arcType>
vertexType Graph<vertexType,arcType>::Getvalue(int v){
	if(v<0||v>=Vertexes.length)
		return NULL;
	else return vertexes.get(v+1);
}
template<class vertexType,class arcType>arcType Graph<vertexType,arcType>::
GetWeight(int v1,int v2){
	if(v1<0||v1>=Vertexes.len||v2<0||v2>=Vertexes.len)
		return NULL;
	else return Arc[v1][v2];
}
template<class vertexType,class arcType>int Graph<vertexType,arctype>::GetFirstNeighbor(const int v){
	if(v>=0&&v<Vertexes.len){
		for(int j=0;j<Vertexes.len;j++)
		{if(Arcs[v][j]==1)
		return j;}
	}
	return -1;
}
template<class vertexType,class arcType>int Graph<vertexType,arcType>::GetNextNeighbor(vertexType a,vertexType b){
	int v1=GetvertexPos(a);
	int v2=GetvertexPos(b);
	if(v1>=0&&v1<Vertexes.len&&v2<Vertexes.len){
		for(int =v2+1;j<Vertexes.len;j++)
			if(Arcs[v1][j]==1)
				return j;
	}
	return -1;
}
	template<class vertexType,class arcType>
		int Graph<vertexType,arcType>::GetVertexPos (vertexType & v){
		if(vertexes.locate(v)==0)return -1;
		else return 1;
	}
	template<class vertexType,class arcType>int Graph<vertexType,arcType>::InsertVertex(vertexType &v){
		return Vertexes.insert(v,Vertexes.len);
	}
	template<class vertexType,class arcType>int Graph<vertexType,arcType>::InsertArc (vertexType a,vertexType b,arcType w){
		if(v1<0||v1>=Vertexes.lenth()||v2<0||v2>=Vertexes.length())
			return 0;
		Arc[v1][v2]=w;
		CurrentNumArcs++;
		return 1;
	}
	DeleteVertex(vertexType a){
		int v=GetvertexType(a);
		for(int i=0;i<Vertexes.len;i++)
		{
			if(Arc[i][v]!=0)CurrentNumArcs--;
			if(Arcs[v][i]!=0)CurrentNumArcs--;
		}
		for(int i=v+1;i<Vertexes.len;i++)
		for(int j=0;j<Vertexes.len;j++)
			{
				Arcs[i-1][j]=Arcs[i][j];
				Arcs[j][i-1]=Arcs[j][i];
			}
			for(int i=0;i<Vertexes.len;i++)
			{Arcs[i][Vertexes.len-1]=0;
			Arcs[Vertexes.len-1][i]=0;}
			Vertexes.Delete(v);
	}
template<class vertexType,class arctype>void Graph<vertexType,arcType>::DeleteArc(int v1,int v2)
	{
		if(v1<0||v1>=Vertexes.len||v2<0||v2>=Vertexes.len)
			return 0;
		Arc[v1][v2]=0;
		CurrentNumArcs--;
		return 1;
	}
template<class vertexType,class arcType>void Graph<vertexType,arcType>::Traver()
{
		for(int i=1;i<=vertexes.length();i++)
			cout<<" "<<vertexes.get(i);
		cout<<endl;
}
void main()
{
int vn,an,c,w;
char e,t,h;
cout<<"input the number of vertex"<<endl;
cin>>vn;
Graph<char,int>g(vn);
cout<<"input vertexes"<<endl;
for(int i=0;i<vn;i++)
{
	cin>>e;
g.Insertex(e);
}
cout<<"有向(1)or无向(2)"<<endl;
cin>>c;
if(c==1)
{
	cout<<"input the number of arcsop:"<<endl;
	cin>>an;
	for(i=0;i<an;i++)
	{
		cout<<"input t,h,w"<<endl;
		cin>>t>>h>>w;
		g.InsertArc(t,h,w);
	}
}
 if(c==2)
{
	cout<<"input the number of arc:"<<endl;
	cin>>an;
	for(int i=0;i<an;i++)
	{
		cout<<"input t,h,w:"<<endl;
		cin>>t>>h>>w;
		g.InsertArc(t,h,w);
	}
}
   g.Traver();
    cout<<endl;
}