[数据结构与算法]数据结构|拓扑排序

拓扑排序

限定：有向无环图

①从DAG图中选择入度为0的顶点，并输出

②从图中删除该入度为0的顶点以及所有以它为起点的边

③重复①和②直到当前图为空，或者图不存在入度为0的顶点。前者输出的序列就是拓扑序列，后者说明图中有环，不存在拓扑序列

典型例题

判断能否构成有向无环图

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;

const int MAXN = 500;

vector<int> graph[MAXN];
int inDegree[MAXN];//入度

bool TopologicalSort(int n) {
    queue<int> node;
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) node.push(i);
    }
    int number = 0;//拓扑序列顶点个数
    while (!node.empty()) {
        int u = node.front();
        node.pop();
        number++;//拓扑序列顶点加1
        for (int i = 0; i < graph[u].size(); i++) {
            int v = graph[u][i];
            inDegree[v]--;//后续顶点入度减1
            if (inDegree[v] == 0) node.push(v);
        }
    }
    return n == number;//判断能否产生拓扑序列
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        if (n == 0 && m == 0) break;
        memset(graph, 0, sizeof(graph));//初始化图
        memset(inDegree, 0, sizeof(inDegree));//初始化入度
        while (m--) {
            int from, to;
            scanf("%d%d", &from, &to);
            graph[from].push_back(to);//注意只有一边
            inDegree[to]++;
        }
        if (TopologicalSort(n)) printf("YES\n");
        else printf("No\n");
    }
    return 0;
}

确定比赛名次

第一行N队伍数目、M 接下来的M行P1、P2表示P1赢了P2。确定排名先后，当符合条件的排名不唯一时，要求输出编号小的队伍在前

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;

const int MAXN = 501;
vector<int> graph[MAXN];
int inDegree[MAXN];// 入度

vector<int> TopologicalSort(int n) {//拓扑排序
    vector<int> topology;//拓扑序列
    priority_queue<int, vector<int>, greater<int>> node;//定义优先序列(需要输出编号小的在前的序列）
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) node.push(i);
    }
    while (!node.empty()) {
        int u = node.top();
        node.pop();
        topology.push_back(u);//加入拓扑序列
        for (int i = 0; i < graph[u].size(); i++) {
            int v = graph[u][i];
            inDegree[v]--;//后继结点入度减1
            if (inDegree[v] == 0) node.push(v);
        }
    }
    return topology;//返回拓扑序列
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        memset(graph, 0, sizeof(graph));
        memset(inDegree, 0, sizeof(inDegree));
        while (m--) {
            int from, to;
            scanf("%d%d", &from, &to);
            graph[from].push_back(to);
            inDegree[to]++;
        }
        vector<int> answer = TopologicalSort(n);
        for (int i = 0; i < answer.size(); i++) {
            if (i == 0) printf("%d", answer[i]);
            else printf(" %d", answer[i]);
        }
        printf("\n");
    }
    return 0;
}