對于給定的AOV網絡，必須先判斷是否存在有向環。

檢測有向環是對AOV網絡構造它的拓撲有序序列，即將各個頂點排列成一個線性有序的序列，使得AOV網絡中所有直接前驅和直接后繼關系都能得到滿足。

這種構造AOV網絡全部頂點的拓撲有序序列的運算叫做拓撲排序，為了實現拓撲排序，需要增加數組count[]記錄各個頂點的入度，并組織一個棧S組織所有入度為0的頂點。每當訪問一個頂點并刪除與它相關聯的邊時，這些邊的另一端點入度減1，入度減至0的結點入棧。

為了建立入度為0的頂點棧，可以不另外分配存儲空間，直接利用入度為0的頂點的count[]數組元素。

設立棧頂指針top，指示當前棧頂（某一個入度為0的頂點）的位置。棧初始化位置為-1，表示空棧。非空棧的棧頂指向次棧頂一直往下指向棧底再指向-1。

如果AOV網絡n頂點e邊。搜索入度為0的結點建立鏈式棧所需時間為O(n)。n個頂點各進棧、出棧、輸出一次，（如果n次循環完成前就?？?span lang="zh-cn">，說明網絡中有回路）。頂點入度減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的入度加1cin>>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; //位于棧頂頂頂點位置記為vtop=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);}} }

?

轉載于:https://www.cnblogs.com/yangyuliufeng/p/9294951.html

總結

以上是生活随笔為你收集整理的算法-图（3）用顶点表示活动的网络（AOV网络）Activity On Vertex NetWork的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。