本讨论 专门 讲解 何为 拓扑排序

本题题解: https://hydro.ac/p/luogu-P2712/solution/68641f28345cc6899b2b6f31

什么是拓扑排序?

是一类典型的图上无权问题 拓扑排序是对有向无环图(DAG, Directed Acyclic Graph)的所有顶点的一种线性排序,使得对于图中的每一条有向边 (u, v),u 在排序中总是位于 v 的前面。如果图中存在环,则无法进行拓扑排序。

例子

无环

比如你期末数学考的非常好,考了0分,你妈高兴的就要拿扫把抽你(别介意,仅为讲解~)

事件A(你考了0分) 事件B(你妈要打你) 事件先后顺序是 事件A -> 事件B 对吧? 对于有先后关系的,可以用图表示 例如1要在2前 可以从2建一个入度(单向边,从1指到2) 这样你只有访问到1才能访问到2 保证 1前2后 以此类推

有环

还是刚刚的例子 你妈高兴的要打你,但是你要喝可乐 事件A 你要喝可乐,喝完你妈才能打你 事件B 你妈要先打你,打完再喝

就有 事件A <-> 事件B 两件事无法排序了?

如上述关系的在图中称为 这叫做 相互依赖

那该怎么写?

基本思路:

1.当然先建图啦!

谁在前就谁向另一项连边 示例: (全部都是 A -> B)

//文件头省略哈
const int maxn = 1000 + 10; // 规定图范围
vector<int> G[maxn]; //此处中括号表示动态数组内的单独数组,类似于二维数组
int ru[maxn]; //记录每个点的入度;

// 省略中间 直击主题
// 假设我们输入了一组数据 a,b,要求 a 在 b 前
G[a].push_back(b); // a的出度(有向边) 出向b
ru[b]++; // b的入度加1;

2.开始

这个特性与queue相似,所以用queue实现较为容易

//那肯定先枚举ru数组内 看有没有0的,如果有0,说明他是第一个元素,加入queue内
queue<int> que;
for(int i=1;i<=ml;i++){
        if(ru[i] == 0){
            que.push(i);
        }
    }
//这样就得到第一个数啦

3.删边与完善

//既然得到了开头,那就继续处理啦
while(!que.empty()){ //队列不空就证明还有不是环的成员
        int now = que.front(); //取队首
        que.pop(); //弹出
        for(auto it : G[now]){ //枚举这个弹出元素的出度
            ru[it]--; //这个元素弹掉了,那原本入度包含这个元素的元素入度就要减1嘛
            if(ru[it] == 0){ //判断,入度为0证明下一个开头是他
                que.push(it); //入队
            }
        }
    }

写法总结

关键点解析 入度(inDegree):指向该节点的边数量

入度为0的节点可以作为拓扑排序的起点

算法流程:

不断移除入度为0的节点

更新剩余节点的入度

重复直到所有节点被处理或发现环

环检测:

如果最终结果包含的节点数 < 总节点数 → 存在环

因为环中的节点入度永远不会降为0

时间复杂度:O(V+E)

每个节点和边只被处理一次

此说明仅为拓扑入门,若有疑问/错误,可以指出

2 comments

  • 1

Information

ID
6746
Time
1000ms
Memory
256MiB
Difficulty
3
Tags
(None)
# Submissions
28
Accepted
5
Uploaded By