【学习】拓扑排序

电玩女神 2023-08-17 16:49 90阅读 0赞

### 前言  ###

这个人太菜了都要CSP了才学拓扑排序

### 0x10 定义 ###

> 给定一张有向无环图，若一个由图中所有点构成的序列A满足边(x,y)，x在A中都出现在y之前，则称A是该有向无环图顶点的一个拓扑序。求解A的过程就叫做拓扑排序。
> 
> 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　　　　　　　　　　　　　　　　　　　　　　　　——蓝书·lyd

### 0x20 思想+过程 ###

选择入度为0的点，然后把他连向的点入读减1就行了

过程：

1.建立空的序列A

2.预处理所有点的入度，把入度为0的点入队

3.取队头x，把x放在A的末尾

4.遍历从x连出的y点，并把y的入度减1，如果这是y的入度为0，入队

5.循环3,4直至队列为空，得到A序列

### 0x30 用处+题目 ###

①判环

②处理图上有明显先后顺序要求的题目

Luogu P1038 神经网络

Luogu P2661 信息传递

### 0x40 code ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 void topsort(){
     2     queue<int>q;
     3     int x,v;
     4     for(int i=1;i<=n;i++){
     5         if(!r[i])q.push(i);//如果入度为零,入队
     6     }
     7     while(!q.empty()){
     8         x=q.front();q.pop();
     9         a[++tot]=x;
    10         for(int i=head[x];i;i=e[i].nxt){
    11             v=e[i].to;--r[v];
    12             if(!r[v])q.push(v);
    13         }
    14     }
    15 }

topsort

转载于:https://www.cnblogs.com/gengyf/p/11604071.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230809/5d7a86fd52ff449da396a8db81a30b8b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，90人围观）

还没有评论，来说两句吧...

相关阅读

相关【学习】拓扑排序

前言这个人太菜了都要CSP了才学拓扑排序 0x10 定义 > 给定一张有向无环图，若一个由图中所有点构成的序列A满足边(x,y)，x在A中都出现在y之前，则称

电玩女神/ 2023年08月17日 16:49/ 0 赞/ 91 阅读

相关拓扑排序

拓扑排序是一张AOV网(Activity Of Vertex NetWork),并且是无环的网! 概念: 设G=(V,E)是一个具有n个顶点的有向图,V中的顶点序列V1,V

墨蓝/ 2022年08月05日 13:11/ 0 赞/ 39 阅读

相关拓扑排序

什么是拓扑排序? 在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序

冷不防/ 2022年06月09日 05:57/ 0 赞/ 236 阅读

相关拓扑排序

In this winter holiday, Bob has a plan for skiing at the mountain resort. This ski

悠悠/ 2022年06月08日 06:19/ 0 赞/ 33 阅读

相关拓扑排序

原文地址：[http://blog.csdn.net/lisonglisonglisong/article/details/45543451][http_blog.csdn.n

曾经终败给现在/ 2022年04月22日 13:00/ 0 赞/ 31 阅读

相关拓扑排序

拓扑排序一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就

小鱼儿/ 2022年04月10日 08:23/ 0 赞/ 258 阅读

相关拓扑排序

（1）有向无环图无环的有向图，简称 DAG (Directed Acycline Graph) 图。有向无环图在工程计划和管理方面的应用：除最简单的情况之外，几

古城微笑少年丶/ 2022年03月18日 12:35/ 0 赞/ 303 阅读

相关拓扑排序

拓扑排序：拓扑排序是根据离散数学中有关偏序与全序定义的。 ![0_1314168765l7fq.gif][] 若一个集合 X 上的关系 R 是自反的反

淩亂°似流年/ 2021年12月23日 02:43/ 0 赞/ 358 阅读

相关拓扑排序

拓扑排序题目做的烦，题解写着玩 [POJ 2762 Going from u to v or from v to u?][POJ 2762 Going from

谁借莪１个温暖的怀抱￠/ 2021年12月20日 16:11/ 0 赞/ 300 阅读

相关拓扑排序

一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程

野性酷女/ 2021年09月19日 05:04/ 0 赞/ 467 阅读