拓扑排序

定个小目标啊，这几天学会它

拓扑排序

拓扑排序是一个排序规则，求的是一个序列，并且序列不唯一

定义

• 在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。

• 且该序列必须满足下面两个条件：

  • 1、 每个顶点出现且只出现一次。
  • 2、 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

​

​

**注意：只有有向无环图（DAG）才有拓扑排序**

用处

• 判断有向图是否有回路出现

思想

• （1）在有向图中把所有入度为0的节点入队列；
• （2）从队列中取得入队为0的节点并进行输出，并让所有以它为头的边的尾节点入度减1；
• （3）重复（1）、（2）两步，直至全队列为空。

注意

拓扑排序过程中，队列中的元素始终唯1个，则拓扑排序序列唯一，反之，不然！！！

代码实现

#include <stdio.h>
#include <stdlib.h>

const int MAX_N = 1e5 + 5;

int q[MAX_N], ans[MAX_N]; //队列, 拓扑排序序列 
int head[MAX_N], v[MAX_N], next[MAX_N], to[MAX_N], pen[MAX_N], edge_cnt; // 构造链式前向星
int n, cnt_ans;

inline void add_edge(int a, int b, int c) { //a->b = c
    to[++edge_cnt] = b;
    v[edge_cnt] = c;
    next[edge_cnt] = head[a];
    head[a] = edge_cnt;
    
    ++pen[b]; // b节点入度加一 
}

void input1() {
    for (int i = 1; i <= n - 1; i++) {
        int a, b, c; // a->b = c
        scanf("%d %d %d", &a, &b, &c);
        add_edge(a, b, c);
    }    
}

void input2() { //默认边权为1 
    for (int i = 1; i <= n - 1; i++) {
        int a, b; // a->b = c
        scanf("%d %d", &a, &b);
        add_edge(a, b, 1);
    }    
}

void output() {
    for (int i = 1; i <= n; i++) {
        for (int j = head[i]; j; j = next[j]) {
            printf("(%d->%d = %d)\t", i, to[j], v[j]);
        }
        putchar('\n');
    }    
    return ;
}

int main() {
    scanf("%d", &n);
    input2();
    int l = 0, r = 0;
    for (int i = 1; i <= n; i++) {
        if (pen[i] == 0) q[r++] = i; //入队列 
    }
    output(); 
    while (l < r) {
        int tp = q[l++];
        ans[cnt_ans++] = tp; // 输出度为0的节点
        for (int i = head[tp]; i; i = next[i]) {
            //printf("%d->%d = %d\n", tp, to[i], v[i]);
             //与节点tp连接的节点入度减一 
            if (--pen[to[i]] == 0) {
                q[r++] = to[i]; // 进行入队
            }
        }
    }
    if (cnt_ans == n) {
        for (int i = 0; i < n; i++) {
            i && putchar(' ');
            printf("%d", ans[i]);
        }
    } else printf("自环\n");
    
    return 0;
}

/*
6
1 3 1000
1 4 10
4 5 50
4 6 100
4 2 100
*/

/*
10
7 5
5 2
2 1
4 10
10 3
3 1
6 8
8 9
9 1
*/

输出所有的拓扑排序序列

利用dfs

#include <stdio.h>
#define MAX_N 1000


int n, m;

int cnt_edge, head[MAX_N], next[MAX_N], to[MAX_N], rudu[MAX_N];

inline void add_edge(int a, int b) {
    ++rudu[b];
    to[++cnt_edge] = b;
    next[cnt_edge] = head[a];
    head[a] = cnt_edge;
    return ;
}

int ans[MAX_N], flag, vis[MAX_N];

void Topological_sorting(const int& cnt) { //dfs 
    if (cnt == n) { //输出拓扑排序序列
        for (int i = 0; i < n; i++) {
            printf("%d", ans[i]);
        }
        flag = 1;
        putchar('\n');
    }
    
    for (int i = 1; i <= n; i++) {
        if (vis[i] || rudu[i]) continue;
        ans[cnt] = i;
        vis[i] = 1;
        for (int j = head[i]; j; j = next[j]) { //与该点连接的点的入度减1 
            --rudu[to[j]];
        }
        Topological_sorting(cnt + 1);
        // 回溯 
        vis[i] = 0;
        for (int j = head[i]; j; j = next[j]) ++rudu[to[j]];//与该点连接的点的入度加1 
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        add_edge(a, b);
    }
    Topological_sorting(0);
    if (flag) printf("No\n"); //存在环 
    return 0;
}

对于输出最小的拓扑排序序列，得用优先队列

完工