拓撲排序是求一個AOV網(頂點代表活動, 各條邊表示活動之間的領先關系的有向圖)中各活動的一個拓撲序列的運算, 可用于測試AOV網絡的可行性. 整個算法包括三步: 1.計算每個頂點的入度, 存入InDegree數組中. 2.檢查InDegree數組中頂點的入度, 將入度為零的頂點進棧. 3.不斷從棧中彈出入度為0的頂點并輸出, 并將該頂點為尾的所有鄰接點的入度減1, 若此時某個鄰接點的入度為0, 便領其進棧. 重復步驟,直到棧為空時為止. 此時, 或者所有頂點都已列出, 或者因圖中包含有向回路, 頂點未能全部列出. 實現代碼: ~~~ #include "iostream" #include "cstdio" #include "cstring" #include "algorithm" #include "queue" #include "stack" #include "cmath" #include "utility" #include "map" #include "set" #include "vector" #include "list" #include "string" using namespace std; typedef long long ll; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; enum ResultCode { Underflow, Overflow, Success, Duplicate, NotPresent, Failure, HasCycle }; template <class T> struct ENode { ENode() { nxtArc = NULL; } ENode(int vertex, T weight, ENode *nxt) { adjVex = vertex; w = weight; nxtArc = nxt; } int adjVex; T w; ENode *nxtArc; /* data */ }; template <class T> class Graph { public: virtual ~Graph() {} virtual ResultCode Insert(int u, int v, T &w) = 0; virtual ResultCode Remove(int u, int v) = 0; virtual bool Exist(int u, int v) const = 0; /* data */ }; template <class T> class LGraph: public Graph<T> { public: LGraph(int mSize); ~LGraph(); ResultCode Insert(int u, int v, T &w); ResultCode Remove(int u, int v); bool Exist(int u, int v) const; int Vertices() const { return n; } void Output(); protected: ENode<T> **a; int n, e; /* data */ }; template <class T> void LGraph<T>::Output() { ENode<T> *q; for(int i = 0; i < n; ++i) { q = a[i]; while(q) { cout << '(' << i << ' ' << q -> adjVex << ' ' << q -> w << ')'; q = q -> nxtArc; } cout << endl; } cout << endl << endl; } template <class T> LGraph<T>::LGraph(int mSize) { n = mSize; e = 0; a = new ENode<T>*[n]; for(int i = 0; i < n; ++i) a[i] = NULL; } template <class T> LGraph<T>::~LGraph() { ENode<T> *p, *q; for(int i = 0; i < n; ++i) { p = a[i]; q = p; while(p) { p = p -> nxtArc; delete q; q = p; } } delete []a; } template <class T> bool LGraph<T>::Exist(int u, int v) const { if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return false; ENode<T> *p = a[u]; while(p && p -> adjVex != v) p = p -> nxtArc; if(!p) return false; return true; } template <class T> ResultCode LGraph<T>::Insert(int u, int v, T &w) { if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure; if(Exist(u, v)) return Duplicate; ENode<T> *p = new ENode<T>(v, w, a[u]); a[u] = p; e++; return Success; } template <class T> ResultCode LGraph<T>::Remove(int u, int v) { if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure; ENode<T> *p = a[u], *q = NULL; while(p && p -> adjVex != v) { q = p; p = p -> nxtArc; } if(!p) return NotPresent; if(q) q -> nxtArc = p -> nxtArc; else a[u] = p -> nxtArc; delete p; e--; return Success; } template <class T> class ExtLgraph: public LGraph<T> { public: ExtLgraph(int mSize): LGraph<T>(mSize) {} void TopoSort(int *order); private: void CallInDegree(int *InDegree); /* data */ }; template <class T> void ExtLgraph<T>::TopoSort(int *order) { int *InDegree = new int[LGraph<T>::n]; int top = -1; // 置棧頂指針為-1, 代表空棧 ENode<T> *p; CallInDegree(InDegree); // 計算每個頂點的入度 for(int i = 0; i < LGraph<T>::n; ++i) if(!InDegree[i]) { // 圖中入度為零的頂點進棧 InDegree[i] = top; top = i; } for(int i = 0; i < LGraph<T>::n; ++i) { // 生成拓撲排序 if(top == -1) throw HasCycle; // 若堆棧為空, 說明圖中存在有向環 else { int j = top; top = InDegree[top]; // 入度為0的頂點出棧 order[i] = j; cout << j << ' '; for(p = LGraph<T>::a[j]; p; p = p -> nxtArc) { // 檢查以頂點j為尾的所有鄰接點 int k = p -> adjVex; // 將j的出鄰接點入度減1 InDegree[k]--; if(!InDegree[k]) { // 頂點k入度為0時進棧 InDegree[k] = top; top = k; } } } } } template <class T> void ExtLgraph<T>::CallInDegree(int *InDegree) { for(int i = 0; i < LGraph<T>::n; ++i) InDegree[i] = 0; // 初始化InDegree數組 for(int i = 0; i < LGraph<T>::n; ++i) for(ENode<T> *p = LGraph<T>::a[i]; p; p = p -> nxtArc) // 檢查以頂點i為尾的所有鄰接點 InDegree[p -> adjVex]++; // 將頂點i的鄰接點p -> adjVex的入度加1 } int main(int argc, char const *argv[]) { ExtLgraph<int> lg(9); int w = 10; lg.Insert(0, 2, w); lg.Insert(0, 7, w); lg.Insert(2, 3, w); lg.Insert(3, 5, w); lg.Insert(3, 6, w); lg.Insert(4, 5, w); lg.Insert(7, 8, w); lg.Insert(8, 6, w); int *order = new int[9]; lg.TopoSort(order); cout << endl; delete []order; return 0; } ~~~