算法学习之路|拓扑排序

  1. 云栖社区>
  2. 博客>
  3. 正文

算法学习之路|拓扑排序

kissjz 2018-02-23 23:49:57 浏览7440
展开阅读全文

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。(来自百度百科定义)

如果你学过离散数学就不难理解这定义,如果没学过可能就没法理解,建议先去补补偏序/全序的概念,本篇不会多谈这些理论概念性的东西,想要了解请自行百度。
接下来说下拓扑排序的算法实现:

拓扑排序算法主要是循环执行以下两步,直到不存在入度为0的顶点为止。

(1) 选择一个入度为0的顶点并输出之;
(2) 从网中删除此顶点及所有出边。

循环结束后,若输出的顶点数小于网中的顶点数,则输出“有回路”信息,否则输出的顶点序列就是一种拓扑序列。
废话不多说上代码(用的是c++stl实现的)

vector<int> G[MAXN];  // 邻接表。  
int son[MAXN];          // 入度数。  
void topo(){ 
    queue<int> que; 
    int ok = 0; 
    for (int i = 0; i < n; i++) 
        if (!son[i]) 
            que.push(i);    // 入度为0时入队。  
    while (!que.empty()){ 
        if (que.size() > 1) 
            ok = 1;         // 当队列中个数超多1时,表示有不唯一解。  
        int t = que.front(); 
        que.pop(); 
        cnt--;          //  如果队列为空后,计数器> 0, 说明存在环结构。  
        for (int i = 0; i < G[t].size(); i++) 
            if (--son[G[t][i]] == 0) // 判断减掉当前点的关系后,点的入度是否为0。  
                que.push(G[t][i]); 
    } 
}

网友评论

登录后评论
0/500
评论
kissjz
+ 关注