拓扑排序与入度

发表于 更新于 分类于

最近在阅读清华大学的数据结构教材时，发现其中对于拓扑排序的更为易懂的实现。

拓扑排序，之前也写过，即为一种将杂乱无章的调度问题规划为一个线性的有序排列的排序算法，其中书上是这么描述的:

什么是拓扑排序？简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

说实话如果对离散数学不太了解，突然一看还是很难懂的。不过其中对于该排序的实现则很简单易懂。

入度

入度，这个概念其实很简单，之前所说拓扑排序基本是在有向无环图（即图中路径均是从一个节点指向另一个节点的，且其中不存在循环路径）中产生的，所以必然会有指向某个节点的路径。

其中，被指向的路径的个数则称为入度，也可以想象成被多少个人指着，千夫所指的话这个人的入度就是这个千了。其中入度为0的节点（即没有路径指向该节点）则可以被视为起点，还是应用之前的装修例子来表述，那么就是一项可以无需等待其他工程完成的工程，比如砸墙。

同样，出度所描述的就是该节点指向其他节点的路径数。

拓扑排序

有了入度概念的引入拓扑排序就很简单了，简单的说我们就是要将当前可以直接进行的工作进行排序，于是我们可以直接在构造图，或者拿到图的时候，对其进行一个入度的记录并排序，简单的使用对象或数组都可以做到：

1
2
3
4
5
vector<int, int> 

struct Node {
    int in;
}

我们只要找到一个起点，选择他为入度，就可以开始排序。

将起点放入我们拓扑排序的栈顶，然后将该节点所链接的节点的入度均减少1，然后从中找到入度为0的节点，再次进行同样的操作，拓扑排序就简单的完成了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 书中的示意代码
InitStack(S);
for (int i = 0, i < G.vexnum; i++) {
    if (!indegree[i]) Push(S, i); // 查找入度为0的节点
}

count = 0;
while (!StackEmpty(S)) {
    Pop(S, i); // 取出入度为0的节点
    count++;
    for (Node p = G.verices[i].firstarc; p; p = p->nextarc) {
        k = p->adjvex;
        if (!--indegree[i]) Push(S, k); // 入度减为0，则入栈
    }
}

if (count < G.vexnum) return ERROR;