graph2.h

1

#include<iostream.h>
#include<iomanip.h>
struct edgenode   //------邻接表中的边节点类型
{
	int adjvex;
	edgenode *next;
};
class GAdjoin{
public:
	int MaxValue;
	int VertexNum;
	int EdgeNum;
    bool visited[50];
	edgenode* adjlist[50];
    edgenode*p;
	void InitAdjoin();
    void CreateAdjoin();//---------------创建图的邻接表
	void PrintAdjoin();//-------------输出图的邻接表
	void Toposort(); //------------输出图的拓扑序列
};

void GAdjoin::InitAdjoin(){
	int v,e;
	cout<<endl;
	cout<<"请输入顶点数：";
	cin>>v;
	VertexNum=v;
	cout<<endl;
	for(int i=0;i<=v;i++){
		
		adjlist[i]=NULL;
	
	}
    cout<<"请输入边数：";
	cin>>e;
	EdgeNum=e;
    
}
void GAdjoin::CreateAdjoin(){
	int fromvex,endvex,e;
	cout<<endl;
	cout<<"请输入"<<EdgeNum<<"条边(两端点序号)："<<endl;
    for(e=0;e<EdgeNum;e++){
		cin>>fromvex>>endvex;
		p=new edgenode;
		p->adjvex=endvex;
		p->next=adjlist[fromvex];
		adjlist[fromvex]=p;
	}
}
void GAdjoin::PrintAdjoin(){
     
	 
	for(int i=0;i<VertexNum;i++){
		cout<<'v'<<i;
		p=adjlist[i];
		while(p!=NULL){
			cout<<"->"<<p->adjvex;
			p=p->next;
		}
	cout<<endl;
	}
}
void GAdjoin::Toposort(){
	int i,j,k,top,m=0;
	edgenode* p;
	int* d=new int[VertexNum];
	for(i=0;i<VertexNum;i++)
		d[i]=0;
	for(i=0;i<VertexNum;i++){
		p=adjlist[i];
		while(p!=NULL){
			j=p->adjvex;
			d[j]++;
			p=p->next;
		}
	}
	top=-1;
	for(i=0;i<VertexNum;i++)
		if(d[i]==0){
			d[i]=top;
			top=i;
		}
	while(top!=-1){
		j=top;
		top=d[top];
		cout<<j<<' ';
		m++;
		p=adjlist[j];
		while(p!=NULL){
			k=p->adjvex;
			d[k]--;
			if(d[k]==0){
				d[k]=top;
				top=k;
			}
			p=p->next;
		}
	}
	cout<<endl;
	if(m<VertexNum)
		cout<<"The network has a cycle!"<<endl;
	cout<<endl;
}