拓扑排序

定义

拓扑排序的英文名是 Topological sorting。

拓扑排序要解决的问题是给一个图的所有节点排序。

我们可以拿大学选课的例子来描述这个过程,比如学习大学课程中有:单变量微积分,线性代数,离散数学概述,概率论与统计学概述,语言基础,算法导论,机器学习。当我们想要学习 算法导论 的时候,就必须先学会 离散数学概述 和 概率论与统计学概述,不然在课堂就会听的一脸懵逼。当然还有一个更加前的课程 单变量微积分。这些课程就相当于几个顶点 , 顶点之间的有向边 就相当于学习课程的顺序。显然拓扑排序不是那么的麻烦,不然你是如何选出合适的学习顺序。下面将介绍如何将这个过程抽象出来,用算法来实现。

但是如果某一天排课的老师打瞌睡了,说想要学习 算法导论,还得先学 机器学习,而 机器学习 的前置课程又是 算法导论,然后你就一万脸懵逼了,我到底应该先学哪一个?当然我们在这里不考虑什么同时学几个课程的情况。在这里,算法导论 和 机器学习 间就出现了一个环,显然你现在没办法弄清楚你需要学什么了,于是你也没办法进行拓扑排序了。因而如果有向图中存在环路,那么我们就没办法进行 拓扑排序 了。

因此我们可以说 在一个 DAG(有向无环图) 中,我们将图中的顶点以线性方式进行排序,使得对于任何的顶点 的有向边 , 都可以有 的前面。

还有给定一个 DAG,如果从 有边,则认为 依赖于 。如果 有路径( 可达 ),则称 间接依赖于

拓扑排序的目标是将所有节点排序,使得排在前面的节点不能依赖于排在后面的节点。

Kahn 算法

过程

初始状态下,集合 装着所有入度为 的点, 是一个空列表。

每次从 中取出一个点 (可以随便取)放入 , 然后将 的所有边 删除。对于边 ,若将该边删除后点 的入度变为 ,则将 放入 中。

不断重复以上过程,直到集合 为空。检查图中是否存在任何边,如果有,那么这个图一定有环路,否则返回 中顶点的顺序就是拓扑排序的结果。

首先看来自 Wikipedia 的伪代码

实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is not empty do
    remove a node n from S
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else
    return L (a topologically sorted order)

代码的核心是维持一个入度为 0 的顶点的集合。

可以参考该图

topo

对其排序的结果就是:2 -> 8 -> 0 -> 3 -> 7 -> 1 -> 5 -> 6 -> 9 -> 4 -> 11 -> 10 -> 12

时间复杂度

假设这个图 在初始化入度为 的集合 的时候就需要遍历整个图,并检查每一条边,因而有 的复杂度。然后对该集合进行操作,显然也是需要 的时间复杂度。

因而总的时间复杂度就有

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int n, m;
vector<int> G[MAXN];
int in[MAXN];  // 存储每个结点的入度

bool toposort() {
  vector<int> L;
  queue<int> S;
  for (int i = 1; i <= n; i++)
    if (in[i] == 0) S.push(i);
  while (!S.empty()) {
    int u = S.front();
    S.pop();
    L.push_back(u);
    for (auto v : G[u]) {
      if (--in[v] == 0) {
        S.push(v);
      }
    }
  }
  if (L.size() == n) {
    for (auto i : L) cout << i << ' ';
    return true;
  } else {
    return false;
  }
}

DFS 算法

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// C++ Version
using Graph = vector<vector<int>>;  // 邻接表

struct TopoSort {
  enum class Status : uint8_t { to_visit, visiting, visited };

  const Graph& graph;
  const int n;
  vector<Status> status;
  vector<int> order;
  vector<int>::reverse_iterator it;

  TopoSort(const Graph& graph)
      : graph(graph),
        n(graph.size()),
        status(n, Status::to_visit),
        order(n),
        it(order.rbegin()) {}

  bool sort() {
    for (int i = 0; i < n; ++i) {
      if (status[i] == Status::to_visit && !dfs(i)) return false;
    }
    return true;
  }

  bool dfs(const int u) {
    status[u] = Status::visiting;
    for (const int v : graph[u]) {
      if (status[v] == Status::visiting) return false;
      if (status[v] == Status::to_visit && !dfs(v)) return false;
    }
    status[u] = Status::visited;
    *it++ = u;
    return true;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Python Version
from enum import Enum, auto


class Status(Enum):
    to_visit = auto()
    visiting = auto()
    visited = auto()


def topo_sort(graph: list[list[int]]) -> list[int] | None:
    n = len(graph)
    status = [Status.to_visit] * n
    order = []

    def dfs(u: int) -> bool:
        status[u] = Status.visiting
        for v in graph[u]:
            if status[v] == Status.visiting:
                return False
            if status[v] == Status.to_visit and not dfs(v):
                return False
        status[u] = Status.visited
        order.append(u)
        return True

    for i in range(n):
        if status[i] == Status.to_visit and not dfs(i):
            return None

    return order[::-1]

时间复杂度: 空间复杂度:

合理性证明

考虑一个图,删掉某个入度为 的节点之后,如果新图可以拓扑排序,那么原图一定也可以。反过来,如果原图可以拓扑排序,那么删掉后也可以。

应用

拓扑排序可以用来判断图中是否有环,

还可以用来判断图是否是一条链。

求字典序最大/最小的拓扑排序

将 Kahn 算法中的队列替换成最大堆/最小堆实现的优先队列即可,此时总的时间复杂度为

习题

CF 1385E:需要通过拓扑排序构造。

Luogu P1347: 拓扑排序模板。

参考

  1. 离散数学及其应用。ISBN:9787111555391
  2. https://blog.csdn.net/dm_vincent/article/details/7714519
  3. Topological sorting,https://en.wikipedia.org/w/index.php?title=Topological_sorting&oldid=854351542

评论