拓扑排序是求一个AOV网(顶点代表活动, 各条边表示活动之间的率先关系的有向图)中各活动的一个拓扑序列的运算, 可用于測试AOV
网络的可行性.
整个算法包含三步:
1.计算每一个顶点的入度, 存入InDegree数组中.
2.检查InDegree数组中顶点的入度, 将入度为零的顶点进栈.
3.不断从栈中弹出入度为0的顶点并输出, 并将该顶点为尾的全部邻接点的入度减1, 若此时某个邻接点的入度为0, 便领其进栈. 反复步骤
3, 直到栈为空时为止. 此时, 或者所有顶点都已列出, 或者因图中包括有向回路, 顶点未能所有列出.
实现代码:
#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的出邻接点入度减1InDegree[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;
}
