对于给定的AOV网络,必须先判断是否存在有向环。
检测有向环是对AOV网络构造它的拓扑有序序列,即将各个顶点排列成一个线性有序的序列,使得AOV网络中所有直接前驱和直接后继关系都能得到满足。
这种构造AOV网络全部顶点的拓扑有序序列的运算叫做拓扑排序,为了实现拓扑排序,需要增加数组count[]记录各个顶点的入度,并组织一个栈S组织所有入度为0的顶点。每当访问一个顶点并删除与它相关联的边时,这些边的另一端点入度减1,入度减至0的结点入栈。
为了建立入度为0的顶点栈,可以不另外分配存储空间,直接利用入度为0的顶点的count[]数组元素。
设立栈顶指针top,指示当前栈顶(某一个入度为0的顶点)的位置。栈初始化位置为-1,表示空栈。非空栈的栈顶指向次栈顶一直往下指向栈底再指向-1。
如果AOV网络n顶点e边。搜索入度为0的结点建立链式栈所需时间为O(n)。n个顶点各进栈、出栈、输出一次,(如果n次循环完成前就栈空,说明网络中有回路)。顶点入度减1的运算执行了e次,所以总时间复杂度为O(n+e)。
template <class T,class E> void TopologicalSort(Graph<T,E>& G){ int i,j,w,v; int top=-1; int n=G.NumberOfVerticles(); int *count=new int[n]; //入度数组兼入度为0顶点栈 for(i=0;i<n;i++) count[i]=0; cin>>i>>j; //输入一条从i到j的边 while(i>-1 && i<n && j>-1 && j<n){ G.insertEdge(i,j); count[j]++; //j的入度加1 cin>>i>>j; } for(i=0;i<n;i++) if(count[i]==0){ count[i]=top; //原栈顶元素放在count[i]中 top=i; //top指向新栈顶 } for(i=0;i<n;i++) //n个结点各出栈一次、输出一次 if(top==-1){ //中途栈空,网络中有回路 cout<<"网络中有回路!"<<endl; return; } else { v=top; //位于栈顶顶顶点位置记为v top=count[top]; //top退到次栈顶 cout<<G.getValue(v)<<""<<endl; w=G.GetFirstNeighbor(v); while(w!=-1){ if(--count[w]==0){ //当邻顶点入度为0时 count[w]=top;top=w; //进栈 } w=G.GetNextNeighbor(v,w); } } }