aov网络的topu排序.cpp

AOV的拓扑排序算法

//AOV网络的topu排序

#include < iostream.h > 

/******************图的定义********************/
//边表结点定义
template <typename T>
struct Edge
{
	int AdjVer;
	Edge<T> *next;
};
//顶点表结点定义
template <typename T>
struct Vertex
{
	T data;
	Edge<T> *next;
};
////////////////
//图用邻接表实现
////////////////
template <typename T>
class Graph
{
	private:
		int size ;
		int *inDegree ;
	public:
		Vertex<T> *Array;
		Graph()
		{
			cout<<"				构造有向图"<<endl;
			cout<<endl;
			cout<<"...1..输入节点个数"<<endl;
			int n ;
			cin >> n ;
			size = n;
			//
			Array = new Vertex<T> [size];
			inDegree = new int [size];
			for (int p=0;p<size;p++)
			{
				inDegree[p] = 0;
			}
			cout<<"...2..构造节点"<<endl;
			for (int i=0; i<size; i++)
			{
				cout<<"输入节点"<<i<<"的值"<<endl;
				T temp;
				cin >>temp;
				Array[i].data = temp ;
				Array[i].next = NULL ;
			}
			//
			int edge ;
			cout<<"...3..构造边，输入边数"<<endl;
			cin>>edge;
			cout<<endl;
			for ( int k = 0 ; k<edge ; k++ )
			{
				int i ,j ;
				cout<<"	输入边"<<'\t'<<k+1<<endl;
				cout<<"由节点 ";
				cin >>i;
				cout<<"到节点 ";
				cin>>j;
				inDegree[j] = inDegree[j]+1;
				//
				Edge<T>* TempEdge = new Edge<T>;
				TempEdge->next = NULL;
				TempEdge->AdjVer = j;
				if ( Array[i].next == NULL )
				{
					Array[i].next = TempEdge ;
				}
				else
				{
					Edge<T>* point = NULL;
					point = Array[i].next;
					while ( (*point).next != NULL )
					{	
						point = (*point).next;
					}
					(*point).next = TempEdge;
				}
			}
		}
		int InDegree(int V)
		{
			return inDegree[V];
		}
		void ShowList()
		{	
			cout<<"		.....   邻接表实现图如下   ....."<<endl;
			cout<<endl;
			for ( int l=0; l<size; l++ )
			{
				cout<<"节点 "<<l<<" "<<"数据 "<<Array[l].data<<'\t'<<"相邻节点为  ";
				if ( Array[l].next != NULL )
				{
					Edge<T>* point = Array[l].next ;
					while (1)
					{
						cout<<(*point).AdjVer<<'\t';
						if ( (*point).next==NULL ) break ;
						point = (*point).next ;
					}
					cout<<endl;
				}
				else
				{
					cout<<endl;
				}
			}
		}
		int ReturnSize()
		{
			return size ;
		}
};

/******************Topo排序函数的定义********************/
template <typename T>
void Topo(Graph<T> G)
{
	Edge<T>* p;
	int i,j,Vnum=0,top,k,n=G.ReturnSize();
	int *InDegree = new int [n];
	int *Topo = new int [n];
	for (i=0;i<n;i++)
		InDegree[i] = G.InDegree(i);

	//链式栈，每次取出栈顶top所指元素
	top = -1;
	for (i=0;i<n;i++)
		if (InDegree[i]==0) 
		{
			InDegree[i] = top;
			top = i ;
		}

	cout<<endl;
	cout<<"		*******  产生的拓扑序列为  *******  "<<endl;
	while(top!=-1)
	{
		j = top;
		top = InDegree[top];
		cout<<"节点  "<<j<<"数据  "<<G.Array[j].data<<endl;
		Vnum++;
		p=G.Array[j].next;
		while(p!=NULL)
		{

			k=(*p).AdjVer;
			InDegree[k]--;
			if ( InDegree[k]==0 )
			{
				InDegree[k] = top ;
				top = k;
			}
			p=p->next;
		
		}
	}
	cout<<endl;
	if (Vnum<n)
		cout<<" 此图不能生成拓扑序列"<<endl;
	delete []InDegree;
}

void main()
{
	Graph<char> MyGraph;
	MyGraph.ShowList();
	Topo(MyGraph);
}