有向图的拓扑排序

发表于 更新于 分类于 ，
本文字数： 975

拓扑排序的简要理解

概念：

拓扑排序只存在于有向无环图，排序后的序列满足对于图中任意一条边的起点在序列中一定在终点前（拓扑排序的序列不唯一）

实现方法：

BFS的方法实现，纪录每一个点的入度（作为几条边的终点），首先将入度为0的点入队（入度为0意味着该点之前的点已经被排入序列），然后开始BFS的过程，重复队头出队，将队头相连的点的入度减一，并检查更新后的入度是否为0，如果为0则将其扩展至队头的过程 (数组实现队列的话，数组则保存了拓扑序列，如果使用queue则需要使用另外的数组保存序列)

代码实现：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int h[N], e[N], ne[N], idx, d[N], q[N];

int n, m;

int topo()
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i++)
    {
        if (d[i] == 0)
            q[++tt] = i;
    }
    while (hh <= tt)
    {
        int t = q[hh++];
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            d[j]--;
            if (d[j] == 0)
                q[++tt] = j;
        }
    }
    return tt == n - 1;
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        e[++idx] = y;
        ne[idx] = h[x];
        h[x] = idx;
        d[y]++;
    }
    if (topo())
    {
        for (int i = 0; i < n; i++)
        {
            printf("%d ", q[i]);
        }
    }
    else
        cout << -1;
    return 0;
}