拓扑排序
最后更新于：2022-04-01 20:06:13
对一个**有向无环图**(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
#include
#include
#include
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 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> 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 cycle() const { return sta; }
private:
void dfs(const Digraph &graph, size_t v)
{
on_stack[v] = true;
marked[v] = true;
vector 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 marked;
vector edgeto;
vector on_stack;
stack 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 getPre() const { return pre; }
vector getPost() const { return post; }
stack getReversePost() const { return reverse_post; }
private:
void dfs(const Digraph &graph, size_t v)
{
marked[v] = true;
pre.push_back(v);
vector 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 marked;
vector pre; // 所有顶点的前序排列
vector post; // 所有顶点的后序排列
stack reverse_post; // 所有顶点的逆后序排列
};
/// 拓扑排序，借助于DepthFirstOrder来实现,保证图中没有环
class Topological
{
public:
Topological(const Digraph &graph)
{
DepthFirstOrder dfs(graph);
stack sta = dfs.getReversePost();
while (!sta.empty())
{
order.push_back(sta.top());
sta.pop();
}
}
vector getOrder() const { return order; }
private:
vector 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 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 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::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());
vertaxs++;
}
void Digraph::removeVertax(size_t v)
{
if (v >= arrSize())
return;
vector::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 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 Digraph::adj(size_t v) const
{
if (v < arrSize())
return arr[v];
else
vector();
}
void Digraph::showAdj(size_t v) const
{
if (v >= arrSize())
return;
vector 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版》 图有关章节
';