? ? ??對一個**有向無環圖**(Directed Acyclic Graph簡稱DAG)G進行拓撲排序，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊(u,v)∈E(G)，則u在線性序列中出現在v之前。通常，這樣的線性序列稱為滿足拓撲次序(Topological Order)的序列，簡稱拓撲序列。簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為**拓撲排序**。(摘抄自：[拓撲排序-百度百科](http://baike.baidu.com/link?url=LQa-nm5WHvlG9AFeR27hZOvYN3HCyfgyLZiVFzh6TfULibSs3QGawKSwR5_dzy58dN7fx6H56zGyfoGA57Z2fq))。
? ? ??首先對于一個優先圖需要先判斷是否存在環，然后再進行拓撲排序操作。如何判斷有向圖是否存在環呢，參考：[有向圖是否有環](http://blog.csdn.net/u012796139/article/details/49863539)。
**源代碼**示例：
~~~
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Digraph
{
public:
Digraph(size_t nvertax) : arr(nvertax), vertaxs(nvertax), edges(0) {}
void addEdge(size_t a, size_t b);
void removeEdge(size_t a, size_t b);
void addVertax(size_t v);
void removeVertax(size_t v);
Digraph reverse() const;
vector<size_t> adj(size_t v) const;
void showAdj(size_t v) const;
void showDigraph() const;
size_t edge() const { return edges; }
size_t vertax() const { return vertaxs; }
size_t arrSize() const { return arr.size(); }
private:
vector<vector<size_t>> arr; // 鄰接表
size_t vertaxs; // 頂點個數
size_t edges; // 邊的個數
};
/// 使用深度優先遍歷在有向圖中尋找有向環
class DirectedCycle
{
public:
DirectedCycle(const Digraph &graph) : marked(graph.arrSize()), edgeto(graph.arrSize()), on_stack(graph.arrSize())
{
for (size_t i = 0; i < graph.arrSize(); i++)
marked[i] = on_stack[i] = false;
for (size_t i = 0; i < graph.arrSize(); i++)
{
if (!marked[i])
dfs(graph, i);
}
}
bool hasCycle() const { return !sta.empty(); }
stack<size_t> cycle() const { return sta; }
private:
void dfs(const Digraph &graph, size_t v)
{
on_stack[v] = true;
marked[v] = true;
vector<size_t> vec = graph.adj(v);
for (size_t i = 0; i < vec.size(); i++)
{
if (this->hasCycle())
return;
else if (!marked[vec[i]])
{
edgeto[vec[i]] = v;
dfs(graph, vec[i]);
}
else if (on_stack[vec[i]])
{
for (size_t x = v; x != vec[i]; x = edgeto[x])
sta.push(x);
sta.push(vec[i]);
sta.push(v);
}
}
on_stack[v] = false;
}
vector<bool> marked;
vector<size_t> edgeto;
vector<bool> on_stack;
stack<size_t> sta;
};
/// 有向圖中基于深度優先遍歷的頂點排序，保證圖中沒有有向環
class DepthFirstOrder
{
public:
DepthFirstOrder(const Digraph &graph) : marked(graph.arrSize())
{
for (size_t i = 0; i < marked.size(); i++)
marked[i] = false;
for (size_t i = 0; i < graph.arrSize(); i++)
{
if (!marked[i])
dfs(graph, i);
}
}
vector<size_t> getPre() const { return pre; }
vector<size_t> getPost() const { return post; }
stack<size_t> getReversePost() const { return reverse_post; }
private:
void dfs(const Digraph &graph, size_t v)
{
marked[v] = true;
pre.push_back(v);
vector<size_t> vec = graph.adj(v);
for (size_t i = 0; i < vec.size(); i++)
{
if (!marked[vec[i]])
dfs(graph, vec[i]);
}
post.push_back(v);
reverse_post.push(v);
}
vector<bool> marked;
vector<size_t> pre; // 所有頂點的前序排列
vector<size_t> post; // 所有頂點的后序排列
stack<size_t> reverse_post; // 所有頂點的逆后序排列
};
/// 拓撲排序，借助于DepthFirstOrder來實現,保證圖中沒有環
class Topological
{
public:
Topological(const Digraph &graph)
{
DepthFirstOrder dfs(graph);
stack<size_t> sta = dfs.getReversePost();
while (!sta.empty())
{
order.push_back(sta.top());
sta.pop();
}
}
vector<size_t> getOrder() const { return order; }
private:
vector<size_t> order; // 頂點的拓撲順序
};
int main(void)
{
Digraph graph(13);
graph.addEdge(0, 1); graph.addEdge(0, 5); graph.addEdge(0, 6);
graph.addEdge(2, 0); graph.addEdge(2, 3);
graph.addEdge(3, 5);
graph.addEdge(5, 4);
graph.addEdge(6, 4); graph.addEdge(6, 9);
graph.addEdge(7, 6);
graph.addEdge(8, 7);
graph.addEdge(9, 10); graph.addEdge(9, 11); graph.addEdge(9, 12);
graph.addEdge(11, 12);
cout << graph.vertax() << endl;
cout << graph.edge() << endl;
graph.showDigraph();
cout << endl;
DirectedCycle cycle(graph);
stack<size_t> sta;
if (cycle.hasCycle())
{
cout << "graph has cycle" << endl;
sta = cycle.cycle();
while (!sta.empty())
{
cout << sta.top() << " ";
sta.pop();
}
cout << endl;
}
else
cout << "graph hasn't cycle" << endl;
Topological topo(graph);
vector<size_t> vec = topo.getOrder();
for (size_t i = 0; i < vec.size(); i++)
cout << vec[i] << " ";
cout << endl;
system("pause");
return 0;
}
void Digraph::addEdge(size_t a, size_t b)
{
if (!(a < vertax() && b < vertax()))
return;
arr[a].push_back(b);
edges++;
}
void Digraph::removeEdge(size_t a, size_t b)
{
if (!(a < vertax() && b < vertax()))
return;
vector<size_t>::iterator iter = find(arr[a].begin(), arr[a].end(), b);
if (iter != arr[a].end())
{
arr[a].erase(iter);
edges--;
}
}
void Digraph::addVertax(size_t v)
{
if (v != arrSize())
return;
arr.push_back(vector<size_t>());
vertaxs++;
}
void Digraph::removeVertax(size_t v)
{
if (v >= arrSize())
return;
vector<size_t>::iterator iter;
for (size_t i = 0; i < arrSize(); i++)
{
if (i == v)
{
edges -= arr[i].size(); // 減去頭部是v的邊的個數
arr[i].clear();
vertaxs--;
}
else
{
iter = find(arr[i].begin(), arr[i].end(), v);
if (iter != arr[i].end())
{
arr[i].erase(iter);
edges--;
}
}
}
}
Digraph Digraph::reverse() const
{
Digraph graph(vertax());
vector<size_t> vec;
for (size_t i = 0; i < arrSize(); i++)
{
vec = adj(i);
for (size_t j = 0; j < vec.size(); j++)
{
graph.addEdge(vec[j], i); // 取得該圖的反向圖
}
}
return graph;
}
vector<size_t> Digraph::adj(size_t v) const
{
if (v < arrSize())
return arr[v];
else
vector<size_t>();
}
void Digraph::showAdj(size_t v) const
{
if (v >= arrSize())
return;
vector<size_t> vec = adj(v);
for (size_t i = 0; i < vec.size(); i++)
cout << vec[i] << " ";
cout << endl;
}
void Digraph::showDigraph() const
{
for (size_t i = 0; i < arr.size(); i++)
{
cout << i << ": ";
showAdj(i);
}
}
~~~
**參考資料**：
? ? ? 1、[https://github.com/luoxn28/algorithm_data_structure](https://github.com/luoxn28/algorithm_data_structure)?（里面有常用的數據結構源代碼，圖相關算法在graph文件夾中）
? ? ??2、《算法 第4版》 圖有關章節
