php中文网 | cnphp.com

 找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
热搜: matlab 源码
搜索资源  
php中文网 | cnphp.com 资源中心 图片.png

资源分类

图片.png

 

拓扑排序小结:
首先来理解什么是拓扑排序;拓扑排序简单说是做事情的先后顺序,在现实生活中,人们经常要做连串事情,这些事情之闻有顺序关系或者依赖关系,在做一件事情之前必须先做另一件事,比如安排客人的座位、穿衣服的先后、课程学习的先后等。这些事情都可以抽象为图论中的拓扑排序。

拓扑排序的概念:
设有a、b、c、d等事情,其中a有最高优先级,b、c优先级相同,d是最低优先级,表示为a→(b,c)→d,那么abcd或acbd都是可行的排序。把事情看成图的点,把先后关系看成有向边,问题转化为在图中求一个有先后关系的排序这就是拓扑排序,显然,一个图能进行拓扑排序的完要条件是它是一个有向无环图(DAG)。有环图不能进行拓扑排序,

当然,这里还要普及两个图的简单概念:

出度:从一个点为起点的出去的边的数量为出度;

入度:以一个点为终点出去的边的数量为出度。

从入度和长度的概念上可以看出,如果一个点的入度数量为0,那这个点必定是最前面的点,如果出度等于0,则这个点必定又是最后面的点;

同时,拓扑排序是基于bfs和dfs的思想实现的,我们就来普及一下对于bfs与dfs拓扑排序的实现方式;

1.bfs:

bfs拓扑排序是常用的拓扑排序算法,这个算法是基于队列来实现的

而实现的思想,则是基于无前驱的顶点优先和无后继的顶点优先

1.无前驱的顶点优先:

以此图为例,

实现的步骤主要是:

(1)先找图中入度为0的点,作为起点放进队列,当然,这些点的先后顺序是无所谓的,主要是得有,如果找完一圈都没有发现图纸有度为0的点,那这个图就不是DAG图,不存在拓扑排序;

(2)在找完图中入度为0的节点之后,我们弹出队首元素,并且将队首元素的邻居的度都减一,把度减为0的邻居放进队列

(3)重复以上步骤,直到队列为空;

拿上图来说,会输出acbd,这就是上图的拓扑序列;

当然,如果队列空了,但是依旧是还有别的点没有进入队列,那这个图就不DAG,也就不存在脱坡序列;

2.无后继顶点优先:

将无前驱节点优先的执行反过来就是无后继顶点优先的执行。

2.基于dfs的拓扑排序

dfs是天然的拓扑排序思想的体现,dfs的原理就是一条路走到黑,一直搜素到最后,然后逐层回退,正是点与点的先后关系。

一个DAG,如果只有一个点是0入度的,从这个点开始拓扑排序,返回的顺序是逆序的拓扑排序,

因为递归返回的是最后的点,这里就没有后继点了,逐层回退,最后到起点


为了得到正序的拓扑序列,数据结构中有一个专门对付逆序的线性结构---那就是栈,用栈记录拓扑序列在输出就可以得到正确的拓扑序列;

但是依旧是有一些细节问题:

(1)应该以入度为0的点为起点开始DFS.如何找到它?需要找到它吗?如果有多个入度为0的点呢?
这几个问题其实并不用特别处理。想象有一个虚拟的点 v,,它单向连接到所有其他点。这个点就是图中唯一 的0入度点,图中所有其他的点都是它的下一层递归,而且它不会把原图变成环路。从这个虚拟点开始DFS就完成了拓扑排序。但运算的时候并不需要处理这个虚拟点,只要在主程序中把每个点轮流执行一 DFS可这样做相当于显式地道归了虚点的所有下一层点,

(2)如果图不是DAG,能判断吗?
图不是DAG,说明图是有环图,不存在拓扑排序。(那么在递归的时候会出现回退边)
在程序中这样发现回退边:记录每个点的状态,如果dfs递归到某个点时发现它仍在前面的递归中没有处理完毕,说明存在回退边,不存在拓扑排序:

还要一些杂项问题:

输出字典序最小的拓扑排序;

这种题目比如杭电1285和北大1270都有体现;

解决这里问题,核心是在当前步骤,在所有入度为0的点中输出编号最小的,

这里我们不用next_permutation();

这里采用的是优先队列:

在bfs拓扑排序中,把普通队列改为优先队列,放进入度为0的节点,每次输出最小编号........就是重复bfs拓扑排序的步骤啦

题目实战:https://www.dotcpp.com/oj/problem1707.html

这道题前面我已发博客:https://www.cnblogs.com/LQS-blog/p/16207985.html

来个重量级的:

https://www.acwing.com/problem/content/description/166/

友情提示,这道题不太好做,慎入;

这里只给出代码,今天很晚了,以后找时间专门出篇博客:
[AppleScript] 纯文本查看 复制代码
#include<bits/stdc++.h>
using namespace std;
const int num=30010;
queue<int>q;
int n,m;
vector<int>edge[num];//存图
vector<int>topo;//拓扑序列
int in[num];//入度数组
bitset<num>f[num];//是标准库中的一个固定大小序列,其储存的数据只包含 0/1
int main()
{
    std::ios::sync_with_stdio(false);
    cin>>n>>m;
    for(register int i=0;i<m;i++)//常规存图入度操作
    {
        int a,b;
        cin>>a>>b;
        edge[a].push_back(b);
        in++;
    }
    for(register int i=0;i<n;i++)//把入度为0的点入队
    {
        if(!in)
        q.push(i);
    }
    while(!q.empty())
    {
        int x=q.front();//取队首
        q.pop();
        topo.push_back(x);//存入拓扑序列
        for(register int j=0;j<edge[x].size();j++)//找邻居
        {
            int y=edge[x][j];
            in[y]--;//度减1
            if(!in[y])//找邻居度为0的节点
            q.push(y);
        }
    }
    for(register int i=topo.size()-1;i>=0;i--)
    {
        int x=topo;
        f[x].reset();//置所以位为0
        f[x][x]=1; // x这个点可以到达自己   f[x][x] =表示从 x出发的点,
        for(register int k=0;k<edge[x].size();k++)
        {
            f[x]|=f[edge[x][k]];//x这个点可以到达的点的数量= {x} U {y1} U {y2}..{yn}
        }
    }
    for(register int i=1;i<=n;i++)
    cout<<f.count()<<endl;// f.count() 返回f 中 1的个数
    return 0;
}

php中文网 | cnphp.com ( 赣ICP备2021002321号-2 )

GMT+8, 2022-8-9 06:24 , Processed in 0.091834 second(s), 18 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

申明:本站所有资源皆搜集自网络,相关版权归版权持有人所有,如有侵权,请电邮(fiorkn@foxmail.com)告之,本站会尽快删除。