拓扑排序的两种方法 --- dfs+Kahn

“什么是拓扑排序？什么是拓扑排序？如果你想知道什么是拓扑排序的话，现在就带你研究。”

拓扑排序是对一个有向图的顶点进行排序。它关心的是图中各个顶点的连接关系，这种连接关系也叫拓扑关系，因为它不关心各个顶点的位置与距离。

看起来很抽象，我们举个栗子。
拿一道数学建模（我不会）课上的题目为例，课程和先修课就形成了一种拓扑关系。

实际上 拓扑排序的结果不唯一 。

//Input:
/*7 9 1 2 2 4 2 7 3 2 3 4 3 5 4 6 4 7 5 6*/

三个核心代码是

//dfs
void dfsTopo(int u){
    
    for(int i=0;i<edge[u].size();i++){
     //遍历u未被访问过的邻接点
        int v=edge[u][i];
        if(!vis[v]){
     vis[v]=1; dfsTopo(v); } //对于未被访问的邻接点先标记访问然后再去深搜这个点
    }
    topo[++k]=u; //去掉这一句就是图的深搜算法
}

//用stack模拟dfs
//Kahn of stack
void Kahn(){
    
    stack<int>s;
    for(int i=1;i<=n;i++){
    
        if(!rd[i]){
     s.push(i); vis[i]=1; } //一开始先将图中入度为0的结点压入栈中
    }
    while(!s.empty()){
    
        int u=s.top();s.pop(); //取出栈顶结点
        topo[++k]=u; //取出的栈顶元素入度一定为0，然后根据栈的性质我们可以将这个栈顶元素存入topo[]中
        for(int i=0;i<edge[u].size();i++){
     //遍历u的邻接点
            int v=edge[u][i];
            if(--rd[v]==0){
     s.push(v); vis[v]=1; } //如果入度为0则压入栈中
        }
    }
}

//Kahn of priority_queue
void Kahn(){
    
    priority_queue<int,vector<int>,greater<int>>q;
    for(int i=1;i<=n;i++){
    
        if(!rd[i]){
     q.push(i); vis[i]=1; dp[i]=1; }
    }

    while(!q.empty()){
    
        int u=q.top();q.pop();
        topo[++k]=u;
        for(int i=0;i<edge[u].size();i++){
    
            int v=edge[u][i];
            if(--rd[v]==0){
     q.push(v); vis[v]=1; }
        }
    }
}

//Output:6 7 4 2 1 5 3
#include<bits/stdc++.h>
#define MAXN 1010
using namespace std;
vector<int>edge[MAXN];
int topo[MAXN],vis[MAXN],k;
void dfsTopo(int u){
    
    for(int i=0;i<edge[u].size();i++){
    
        int v=edge[u][i];
        if(!vis[v]){
     vis[v]=1; dfsTopo(v); }
    }
    topo[++k]=u;
}
int main(){
    
    int n,m,u,v;
    cin>>n>>m;
    for(int i=0;i<m;i++){
    
        cin>>u>>v;
        edge[u].push_back(v);
    }
    for(int i=1;i<=n;i++){
    
        if(!vis[i])dfsTopo(i);
    }
    for(int i=1;i<=n;i++)cout<<topo[i]<<" ";
    return 0;
}

//Output:3 5 1 2 4 7 6
#include<bits/stdc++.h>
#define MAXN 1010
using namespace std;
vector<int>edge[MAXN];
int topo[MAXN],vis[MAXN],k,rd[MAXN];//rd[]记录入度数
int n;
void Kahn(){
    
    stack<int>s;
    for(int i=1;i<=n;i++){
    
        if(!rd[i]){
     s.push(i); vis[i]=1; }
    }
    while(!s.empty()){
    
        int u=s.top();s.pop();
        topo[++k]=u;
        for(int i=0;i<edge[u].size();i++){
    
            int v=edge[u][i];
            if(--rd[v]==0){
     s.push(v); vis[v]=1; }
        }
    }
}
int main(){
    
    int m,u,v;
    cin>>n>>m;
    for(int i=0;i<m;i++){
    
        cin>>u>>v; rd[v]++;
        edge[u].push_back(v);
    }
    Kahn();
    for(int i=1;i<=n;i++)cout<<topo[i]<<" ";
    return 0;
}

//Output:1 3 2 4 5 6 7
//对照上面的图，我们会发现，1 3 是第一层，2 4 5 是第二层，6 7是第三层
#include<bits/stdc++.h>
#define MAXN 5050
using namespace std;
vector<int>edge[MAXN];
int topo[MAXN],vis[MAXN],k,rd[MAXN];//rd[]记录入度数
int n;
void Kahn(){
    
    priority_queue<int,vector<int>,greater<int>>q;
    for(int i=1;i<=n;i++){
    
        if(!rd[i]){
     q.push(i); vis[i]=1; }
    }
    while(!q.empty()){
    
        int u=q.top();q.pop();
        topo[++k]=u;
        for(int i=0;i<edge[u].size();i++){
    
            int v=edge[u][i];
            if(--rd[v]==0){
     q.push(v); vis[v]=1; }
        }
    }
}
int main(){
    
    int m,u,v;
    cin>>n>>m;
    for(int i=0;i<m;i++){
    
        cin>>u>>v;
        edge[u].push_back(v);
        rd[v]++;
    }
    Kahn();
    for(int i=1;i<=n;i++)cout<<topo[i]<<endl;
    return 0;
}