Yukang's Page

拓扑排序

2013-11-20

最近在看一些图算法,发现拓扑排序频繁出现,这里写一下自己的一些总结。

拓扑排序是对于有向无环图而言的(DAG),就是对于这个图所有的点(V1, V2, … Vn)找到一个点序列使得任意边(u, v), u出现在v的前面。很容易证明,如果一个有向图中有环那么不存在拓扑排序。

现实中的问题

首先来看现实中哪些问题需要拓扑排序的,课程排序,编译依赖问题,类似的凡是涉及到相关顺序的时间安排,比如Rails里面的初始化调用了库Tsort来进行排序。Unix中有个命令也叫tsort),在有的makefile里面还直接使用了这个命令来解决依赖问题。

O(V+E)的算法

topologicalsort

拓扑排序的基本算法是用DFS,我们希望把有出度的点尽量排在前面,所以这里需要注意和DFS的区别。比如上面图中的一个DFS访问顺序是: 5 2 3 1 0 4, 但是这不是一个拓扑排序,4需要排在0的前面,5, 4, 0, 2, 3, 1。
拓扑排序中需要等迭代完节点的连接邻点后再把当前点压入栈。

#include <iostream>
#include <stdio.h>
#include <list>
#include <stack>
using namespace std;
class Graph {
int V;
list<int>* adj;
void _topological_sort(int v, bool visited[], stack<int>& stack);
public:
Graph(int v);
~Graph();
void addEdge(int v, int w);
void Topological_sort();
};
Graph::Graph(int v):V(v) {
adj = new list<int>[V];
}
Graph::~Graph() {
delete [] adj;
}
void Graph::addEdge(int v, int w) {
adj[v].push_back(w);
}
void Graph::_topological_sort(int v, bool visited[], stack<int>& stack) {
visited[v] = true;
for(list<int>::iterator it = adj[v].begin(); it != adj[v].end(); ++it) {
int u = *it;
if(visited[u] == false)
_topological_sort(u, visited, stack);
}
stack.push(v);
}
void Graph::Topological_sort() {
bool visited[V];
stack<int> stack;
for(int i=0; i<V; i++)
visited[i] = false;
for(int i=V-1; i>=0; i--) {
if(visited[i] == false) {
_topological_sort(i, visited, stack);
}
}
while(!stack.empty()) {
int v = stack.top();
stack.pop();
std::cout << " " << v << " ";
}
std::cout << std::endl;
}
int main() {
Graph g(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
cout << "Following is topological sort result: \n";
g.Topological_sort();
return 0;
}

唯一性

如果一个DAG的拓扑排序中任意连续的两点都是可连通的,那么这个序列也就是DAG的Hamiltonian路径,而且如果DAG图的Hamiltonian路径存在,那么拓扑排序就是唯一的。否则如果一个拓扑排序结果不是Hamiltonian路径,那么就存在多个拓扑排序结果。

其他图算法的预处理

  • DAG的强连通分支问题
    先得到拓扑排序,形成逆向图(所有边与原来方向相反),然后根据拓扑排序依次再进行DFS。

  • DAG的最短路径问题,这可以在O(V+E)复杂度解决最短路径问题。同样类似的算法适用与DAG的最长路径问题,给定一个点求DAG中的各个点与给定点之间的最长路径。最长路径问题要比最短路径问题难,因为最长路径问题没有最优子结构,对于通用的图的最长路径算法还是NP难的问题

使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章