AOV网络的topu排序.rar_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); }