美文网首页
算法学习之拓扑排序

算法学习之拓扑排序

作者: Steven1997 | 来源:发表于2018-04-10 00:01 被阅读297次

拓扑排序的理解

拓扑排序的定义:

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。
首先理解排序的规则:即若存在一条有向边从u到v,则在排序后的顺序里u在v的前面。并且每个点在这个拓扑序里只能出现一次。考虑为什么必须是有向无环图,首先无向显然是不行的,而如果存在环,则会存在冲突的前后关系。



对于这样一张图显然我们根据定义可得其拓扑序为:{1,2,4,3,5}。但是对于下面这张:



那么v2,v3谁在前面了?答案是都可以。于是有了两种拓扑序:{v1,v2,v3,v4}或{v1,v3,v2,v4}。
于是我们可以知道,一个有向无环图可以有一个或多个拓扑排序序列,通常顺序会取决于我们求解的过程。

拓扑排序的解法

方法1:寻找入度为0的点

1、读入时记录每个点的入度。
2、遍历出所有入度为0的点,加入队列。
3、从队列里依次选择一个点,删除它的所有出边,将边连向的点入度减1。
4、执行3操作时判断入度减1后是否入度变为0,如果入度为0,加入队列。
5、重复执行3、4操作至所有点全部被处理。

如图:


关键代码:
for(int i = 1;i <= n;i++)
        if(in[i]==0)
            q.push(i);
while(!q.empty()){
        int u = q.front();
        q.pop();
        //printf("%d ",u);在这个时候输出要求的拓扑序
    int len = G[u].size();
        for(int i = 0;i < len;i++){
        int to = G[u][i];
            in[to]--;
            if(in[to] == 0) 
        q.push(to);
        }
}

注意:如果最后输出的拓扑序的顶点数小于总顶点数,则表明存在有向环;反之,则是DAG,只要任意时刻出现队列中元素个数大于1的情况,就有多个拓扑序。如果任意时刻队列中元素的个数始终为1,则有唯一的拓扑序。

方法2:dfs

其实就是在dfs的时候,对于一个点,在返回上一个调用处时,将其加入一个数组。最后答案就是这个数组的逆序。考虑正确性,对于一个点v,它将指向许多点,当这些点已经处理完后,v将返回上一个指向它的点的u,因为v指向的点必然在其后面,而u必然在它前面,所以依次加入他们是符合拓扑序的,只不过是逆序的。

关键代码:

void dfs(int u){
    int len = G[u].size();
    for(int i = 0;i < len;i++){
    int to = G[u][i];
        if(!vis[to]){
            vis[to] = true;
            dfs(to);
        }
    }
        
    ans[++num] = u;//注意答案是这个数组的逆序
}

int main(){
    for(int i = 1;i <= n;i++)
        if(!vis[i]){
            vis[i]=true;
            dfs(i); 
        }   
}

模板例题:http://blog.csdn.net/qianguch/article/details/77412866

参考博客:https://blog.csdn.net/qianguch/article/details/77411160

相关文章

  • 7.6图的应用:拓扑排序

    拓扑排序Topological Sort ❖从工作流程图得到工作次序排列的算法,称为“拓扑排序”❖拓扑排序处理一个...

  • 模板

    并查集 拓扑排序 Floyd算法 Dijkstra算法

  • LeetCode 第207题:课程表

    1、前言 2、思路 使用拓扑排序的方法,拓扑排序其实是使用的 BFS 算法,简而言之使用 BFS 算法解题。算法流...

  • 算法学习之拓扑排序

    拓扑排序的理解 拓扑排序的定义: 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行...

  • 18-拓扑排序

    拓扑排序## 拓扑排序是针对有向无环图定义的,此算法可以判断一个有向图是否存在回路。拓扑排序反应的是活动和工程的先...

  • 拓扑排序就这么回事

    前言 大家好,这里是《齐姐聊算法》系列之拓扑排序问题。 Topological sort 又称 Topologic...

  • 拓扑排序算法

    拓扑排序定义对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有...

  • Python:12多重继承

    python 多重继承之拓扑排序

  • Lintcode 615. Course Schedule

    题目求先修课程有没有冲突,算法是用bfs, 拓扑排序 拓扑排序:找到有向图中,从头到尾的一种排序,所以中间没有环路...

  • 强连通分量和Kosaraju算法

    内容概要: 基于深度优先后序遍历的DAG图拓扑排序 强连通分量 求解强连通分量Kosaraju算法 拓扑排序的另一...

网友评论

      本文标题:算法学习之拓扑排序

      本文链接:https://www.haomeiwen.com/subject/yrnwhftx.html