Topological-Sort

TopSort

Posted by Haven Tong on 2020-03-06

拓扑排序

近日实现了一下拓扑排序,在这里记录一下拓扑排序的思想,并附上一个具体的题目

这里使用bfs实现

思想

对一个有向无环图(DAG-Directed Acyclic Graph)G进行拓扑排序,将G中的所有顶点拍成一个线性序列,使得图中任何一对顶点u和v,若(u, v) 属于 E(G),则u在线性序列中出现在v之前。

也就是说,由某集合上的偏序得到这个集合的全序

步骤

  1. 计算所有节点的入度(in-degree)
  2. 将所有入度为0的节点加入一个队列
  3. 然后出队,得到一个元素
  4. 将该元素指向的所有节点的入度都减1
  5. 在减的过程中,如果其减后为0则将该元素也加入队列
  6. 继续进行步骤3,直到队列为空

运用

除了以上提到的用途,还可以判断有向图中是否有环:

根据出队元素的个数,若出队元素的个数等于图中节点的个数,则该图无环;否则该有向图存在环

例题

hdu-1285

题目大意就是进行拓扑排序,来获得比赛的名次,但是名次的排列要按照最小的字典序–即同等排名的元素,编号小的放在前面,这里使用了两种方式

  • 使用priority_queue代替queue

    保证每次出队的元素都是最小的那个,具体AC代码如下:

    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 <vector>
    #include <algorithm>
    #include <queue>
    using namespace std;

    int n, m;

    vector<int> topSort(vector<vector<int> >& G){
    vector<int> result;
    // 记录每个节点的入度
    vector<int> in(n + 1, 0);
    for (int i = 1; i < G.size(); i++) {
    for (int j = 0; j < G[i].size(); j++) {
    in[G[i][j]]++;
    }
    }
    // 使用优先队列,保证每次出队的元素最小
    priority_queue<int, vector<int>, greater<int > > queue;
    // 第一次入队,所有in-degree为0的节点
    for (int i = 1; i < in.size();i ++) {
    if (in[i] == 0) {
    queue.push(i);
    }
    }
    while (!queue.empty()) {
    int current = queue.top();
    queue.pop();
    // 出队元素存到排序结果中
    result.push_back(current);
    // 将所有current指向的节点的in-degree全部-1
    for (int i = 0; i < G[current].size(); i++) {
    in[G[current][i]]--;
    // 如果减到0则入队
    if (in[G[current][i]] == 0) {
    queue.push(G[current][i]);
    }
    }
    }
    return result;
    }

    int main() {
    while (cin >> n >> m) {
    vector<vector<int> > G(n + 1);
    int a, b;
    for (int i = 0; i < m; i++) {
    cin >> a >> b;
    G[a].push_back(b);
    }
    vector<int> result = topSort(G);
    for (int i = 0; i < result.size(); i++) {
    cout << result[i] << ((i == result.size() - 1) ? "" : " ");
    }
    cout << endl;
    }
    }
  • 对于in-degree,每次从头开始寻找in-degree为0的节点,所以每次找到的都是当前编号最小的节点

    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
    #include <iostream>
    #include <vector>
    #include <cstring>
    using namespace std;

    int n, m;
    // 存放结果
    int ans[505];

    void topSort(vector<vector<int>>& G) {
    vector<int> in(n + 1);
    for (int i = 0; i < G.size(); i++) {
    for (int j = 0; j < G[i].size(); j++) {
    in[G[i][j]]++;
    }
    }
    for (int i = 1; i <= n; i++) {
    // 每次从in数组的头部开始查找,那么每次找到的都是当前编号最小的节点
    int k = 1;
    while (in[k] != 0){
    k++;
    }
    ans[i] = k;
    // 将in[k]赋值为-1来表示删除节点
    in[k] = -1;
    // 将k连接的所有节点的in-degree都-1
    for (int j = 0; j < G[k].size(); j++) {
    in[G[k][j]]--;
    }
    }
    }

    int main() {
    while (cin >> n >> m) {
    memset(ans, 0, sizeof(ans));
    int a, b;
    vector<vector<int> > G(n + 1);
    for (int i = 0; i < m; i++) {
    cin >> a >> b;
    G[a].push_back(b);
    }
    topSort(G);
    for (int i = 1; i <= n; i++) {
    cout << ans[i] << ((i == n ) ? "" : " ");
    }
    cout << endl;
    }
    return 0;
    }