首页 > 图论 > 拓扑排序-图论
2014
06-26

拓扑排序-图论

假设我们有一组任务要完成,并且有些任务要在其它任务完成之后才能开始,所以我们必须非常小心这些任务的执行顺序。
如果这些任务的执行顺序足够简单的话,我们可以用链表来存储它们,这是一个很好的方案,让我们可以准确知道任务的执行顺序。问题是有时候不同任务之间的关系是非常复杂的,有些任务依赖于两个甚至更多的任务,或者反过来很多任务依赖自己。
因此我们不能通过链表或者树的数据结构来对这个问题建模。对这类问题唯一合理的数据结构就是图。我们需要哪种图呢?很显然,我们需要有向图来描述这种关系,而且是不能循环的有向图,我们称之为有向无环图。要通过拓扑排序对图形进行排序,这些图必须是不能循环和有向的。为什么这些图不能循环呢?答案很明显,如果图形是循环的,我们无法知道哪个任务该优先执行,也不可能对任务进行排序。现在我们一要做的是对图中的每个节点排序,组成一条条边(u,v),u在v之前执行。然后我们就可以得到所有任务的线性顺序,并按这种顺序执行任务就一切都OK了。

例如,下面的图的一个拓扑排序是“5 4 2 3 1 0”。一个图可以有多个拓扑排序。
另一个拓扑排序是“4 5 2 3 1 0”。拓扑排序的第一个顶点总是入度为0。

graph

方法一
现在我们可以得到这个算法的基本步骤:

1.构造空列表 L和S;
2.把所有没有依赖节点(入度为0)的节点放入L;
3.当L还有节点的时候,执行下面步骤:
3.1  	L中拿出一个节点n(从L中remove掉),并放入S
3.2  		对每一个邻近n的节点m,
3.2.1 			去掉边(n,m);(表示加入最终结果集S)
3.2.2 			如果m没有依赖节点(入度为零),把m放入L;

核心就是:每次都选取入度为0的节点,再更新其相邻的节点的入度 。

这个是相对比较直观的算法,也是常见的一种算法。我们用一个数组degree[]记录所有顶点的入度。删除点时更新该数组。
参考下面代码函数:topologicalSort1()

方法二
另外一种方法是参考DFS,对图的深度优先遍历做些修改。我们确信在有向图中如果存在一条边(u,v),那么顶点u会先于顶点v进入列表中。因此在深度遍历时,用栈来存储遍历的顺序。参考下面代码的函数:topologicalSort2()

C++实现

// C++实现的拓扑排序算法
#include<iostream>
#include <list>
#include <stack>
using namespace std;

// 图类
class Graph
{
    int V;    //顶点个数

    // 邻接表
    list<int> *adj;
    // 拓扑排序方法 2的辅助函数
    void topologicalSortRecall(int v, bool visited[], stack<int> &Stack);

public:
    Graph(int V);

     // 添加边
    void addEdge(int v, int w);

    //拓扑排序普通方法
    void topologicalSort1();

    // 拓扑排序方法二
    void topologicalSort2();
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); //
}

//类似深度优先遍历,将和V相邻的顶点(且为访问过的)放入栈中
void Graph::topologicalSortRecall(int v, bool visited[], stack<int> &stk)
{
    //标记v为访问过的
    visited[v] = true;

    // 对每个顶点进行递归调用
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            topologicalSortRecall(*i, visited, stk);

    // 保存顶点
    stk.push(v);
}

// 方法二,使用递归调用实现拓扑排序
void Graph::topologicalSort2()
{
    stack<int> stk;
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;

    //每个顶点都调用一次
    for (int i = 0; i < V; i++)
      if (visited[i] == false)
        topologicalSortRecall(i, visited, stk);

    // 打印
    while (stk.empty() == false)
    {
        cout << stk.top() << " ";
        stk.pop();
    }
}

// 方法一
void Graph::topologicalSort1()
{
	list<int>::iterator j;
	int degree[V];
	//遍历所有的边,计算入度
	for(int i=0; i<V; i++){
		degree[i] = 0;
		for (j = adj[i].begin(); j != adj[i].end(); ++j){
			degree[*j]++;
		}
	}
	list<int> zeroNodes;//所有入度为0的点
	list<int> result;//所有入度为0的点
	for(int i=0; i<V; i++){
		if(degree[i] == 0){
			zeroNodes.push_back(i);
		}
	}
	while(zeroNodes.size() > 0){
		int top = zeroNodes.back();
		zeroNodes.pop_back();
		result.push_back(top);
		for (j = adj[top].begin(); j != adj[top].end(); ++j){
			degree[*j]--;//删除和top相邻的边,并更新其它顶点的入度
			if(degree[*j] == 0) zeroNodes.push_back(*j);
		}
	}

	//打印结果
	for(j= result.begin(); j != result.end(); j++)
		cout << (*j) << " ";
}

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 a Topological Sort of the given graph using  topologicalSort1\n";
    g.topologicalSort1();
    cout << endl;
    cout << "Following is a Topological Sort of the given graph using  topologicalSort2\n";
    g.topologicalSort2();
    return 0;
}

参考:http://www.geeksforgeeks.org/topological-sorting/


  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

    • 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯