拓扑排序

介绍

在有向图中，如果存在从顶点 u 到 v 的路径，则不能存在 v 到 u 的路径，也即按照顶点遍历的顺序，u 总排在 v 的前面，说明了图中不能存在环，否则无法进行拓扑排序，所以可以使用拓扑排序来判断有向图中是否存在环。

算法

Kahn 算法

$S$ 初始化为图中所有入度为 0 的顶点集合，$L$ 保存拓扑排序的顶点序列，$E$ 表示图中边的连接情况。
当 $S$ 不为空时，从 $S$ 中取出一个顶点 $u$，将 $u$ 加入到 $L$ 中，删掉所有的边 $uv$，$uv$ 表示 $u$ 指向 $v$，如果 $v$ 的入度变为 0，则将 $v$ 加入 $S$ 中。
循环执行第 2 步，直到 $S$ 为空。
如果 $E$ 中仍然存在边，则说明图中存在环，否则 $L$ 即为得到的拓扑排序结果。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


def topo_sort(n: int, adj: List[List[int]], indeg: List[int], L: List[int]) -> bool:
    # n: 结点数，adj: 邻接表, indeg: 入度，L: 排序结果
    S = [u for u, deg in enumerate(indeg) if deg == 0]
    while S:
        u = S.pop()
        L.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                S.append(v)
    return len(L) == n

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


bool topo_sort(int n, vector<vector<int>> &adj, vector<int> &indeg, vector<int> &L) {
    // n: 结点数，adj: 邻接表, indeg: 入度，L: 排序结果
    vector<int> S;

    for (int u = 0; u < n; ++u) {
        if (indeg[u] == 0) {
            S.emplace_back(u);
        }
    }

    while (!S.empty()) {
        int u = S.back();

        S.pop_back(), L.emplace_back(u);
        for (int v : adj[u]) {
            if (--indeg[v] == 0) {
                S.emplace_back(v);
            }
        }
    }

    return L.size() == n;
}

时间复杂度：$\mathcal{O}(V+E)$
空间复杂度：$\mathcal{O}(V+E)$

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


def topo_sort(n: int, adj: List[List[int]], L: List[int]) -> bool:
    # n: 结点数，adj: 邻接表, L: 排序结果
    vis = [False] * n
    taken = [False] * n

    def has_cycle(u: int) -> bool:
        if taken[u]:
            return False

        if vis[u]:
            return True

        vis[u] = True
        for v in adj[u]:
            if has_cycle(v):
                return True
        vis[u] = False

        taken[u] = True
        L.append(u)

        return False

    for u in range(n):
        if has_cycle(u):
            return False

    L[:] = list(reversed(L))
    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
32
33
34
35
36


bool topo_sort(int n, vector<vector<int>> &adj, vector<int> &L) {
    // n: 结点数，adj: 邻接表, L: 排序结果
    vector<int> vis(n), taken(n);

    function<bool(int)> has_cycle = [&](int u) -> bool {
        if (taken[u]) {
            return false;
        }

        if (vis[u]) {
            return true;
        }

        vis[u] = true;
        for (int v : adj[u]) {
            if (has_cycle(v)) {
                return true;
            }
        }
        vis[u] = false;

        taken[u] = true;
        L.emplace_back(u);

        return false;
    };

    for (int u = 0; u < n; ++u) {
        if (has_cycle(u)) {
            return false;
        }
    }

    reverse(L.begin(), L.end());
    return true;
}

例题

参考

https://en.wikipedia.org/wiki/Topological_sorting