2020-2021:teams:hotpot:toposort
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:toposort [2020/05/06 15:39] misakatao 创建 |
2020-2021:teams:hotpot:toposort [2020/05/17 09:23] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| =====问题概述===== | =====问题概述===== | ||
| - | 拓扑排序是一种一般在有向无环图(DAG)上实现的算法，其主要目的是把这一有向无环图的顶点排列成一个线性的序列，并且对于图中的任意一条单向边$<u,v>$，点$u$在点$v$之前。 | + | 拓扑排序是一种一般在有向无环图(DAG)上实现的算法，其主要目的是把这一有向无环图的顶点排列成一个线性的序列，并且对于图中的任意一条单向边$\langle u,v \rangle$，点$u$在点$v$之前。 |
| =====算法实现===== | =====算法实现===== | ||
| 行 7: | 行 7: | ||
| 拓扑排序的流程如下。 | 拓扑排序的流程如下。 | ||
| - | 我们准备一个空的队列Q，首先我们把所有入度为0的点放入队列，然后我们一次处理队列中的点。每处理一个点，我们把这个点能够到达的所有点的入度舰少一，如果经过这一处理后又有点的入度变为0，那么我们就把它放入队列。这样一来，我们从队列中取出点的序列就是问题概述中所要求得的序列。 | + | 我们准备一个空的队列Q，首先我们把所有入度为0的点放入队列，然后我们一次处理队列中的点。每处理一个点，我们把这个点能够到达的所有点的入度减少一，如果经过这一处理后又有点的入度变为0，那么我们就把它放入队列。这样一来，我们从队列中取出点的序列就是问题概述中所要求得的序列。 |
| =====正确性分析===== | =====正确性分析===== | ||
2020-2021/teams/hotpot/toposort.1588750743.txt.gz · 最后更改: 2020/05/06 15:39 由 misakatao
