【图论】拓扑排序

· · 算法·理论

【1】DAG,拓扑序的定义

对于一个有向无环图，我们称其为 DAG。

拓扑排序是一个有向无环图的所有顶点的线性序列。

该序列需要满足每个顶点出现且只出现一次和如果有一条 A 到 B 的路径，在序列中 A 出现在 B 的前面。

引用来源

存在环的有向图是不存在拓扑序的。

如何求一个 DAG 的拓扑序呢？

考虑如下算法：

一开始入度为 0 的点一定可以先加入到序列中。

我们将这些点删除，更新其相连节点的入度。

重复上述操作，直到所有节点被删除。

我们用一个数组存储所有点的入度，同时用一个队列。先把所有点扫一遍，把所有度数为 0 的点入队，使用广搜的思想，每次将队头 u 取出，将 u 加入拓扑序列，遍历 u 相连的所有结点 v，将 v 的入度减 1。如果发现当前 v 入度为 0 了，将 v 入队。

直到队列为空。

这里说明一下：如果发现队列空了，拓扑序长度不为点数 n，说明有向图中存在环。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9,M = 1e5 + 9;
struct edge{
    int to,nex;
} e[M];
int head[N],ecnt;
void addedge(int u,int v){
    ecnt++;
    e[ecnt] = (edge){v,head[u]};
    head[u] = ecnt;
}
int n,m;
int deg[N];//入度 
int ans[N],top;
void topsort(){
    queue<int>q;
    for(int i = 1;i <= n;i++)
        if(!deg[i])
            q.push(i);
    while(!q.empty()){
        int u = q.front();
        ans[++top] = u;
        q.pop();
        for(int i = head[u];i;i = e[i].nex){
            int v = e[i].to;
            deg[v]--;
            if(!deg[v])
                q.push(v);
        }
    }
    if(top != n){//存在环
        cout << -1;
        exit(0);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= m;i++){
        int u,v;
        cin >> u >> v;
        addedge(u,v);
        deg[v]++;
    }
    topsort();
    return 0;
}

例题1：家谱树

板子题，修改读入即可。

因为数据量很小，所以用邻接矩阵也可以，同时不需要判环。

#include<bits/stdc++.h>
using namespace std;
const int N = 109,M = 1e4 + 9;
struct edge{
    int to,nex;
} e[M];
int head[N],ecnt;
void addedge(int u,int v){
    ecnt++;
    e[ecnt] = (edge){v,head[u]};
    head[u] = ecnt;
}
int n,m;
int deg[N];//入度 
void topsort(){
    queue<int>q;
    for(int i = 1;i <= n;i++)
        if(!deg[i])
            q.push(i);
    while(!q.empty()){
        int u = q.front();
        cout << u << ' ';
        q.pop();
        for(int i = head[u];i;i = e[i].nex){
            int v = e[i].to;
            deg[v]--;
            if(!deg[v])
                q.push(v);
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i++){
        while(1){
            int v;
            cin >> v;
            if(!v)
                break;
            addedge(i,v);
            deg[v]++;   
        }
    }
    topsort();
    return 0;
}

例题 2：车站分级

图论建模好题。

对于一趟列车中的一个停靠站 u，可以确定 u 到终点站之间所有非停靠站，并且 u 的级别肯定比其中任意一个车站 v 的级别高，因此在 u,v 之间连有向边，用拓扑排序求出 DAG 中的最长链即为最终答案。

#include<bits/stdc++.h>
using namespace std;
const int N = 1009,M = N * N;
int n,m;
bool G[N][N],park[N];
int last[N];
struct edge{
    int to,nex;
} e[M];
int head[N],ecnt;
void addedge(int u,int v){
    ecnt++;
    e[ecnt] = (edge){v,head[u]};
    head[u] = ecnt;
}

int dep[N],ans = 1;

int deg[N];
queue<int> q;
void topsort(){
    for(int i = 1;i <= n;i++)
        if(!deg[i]){
            q.push(i);
            dep[i] = 1;
        }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i = head[u];i;i = e[i].nex){
            int v = e[i].to;
            dep[v] = max(dep[v],dep[u] + 1);
            ans = max(ans,dep[v]);
            deg[v]--;
            if(!deg[v])
                q.push(v);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    while(m--){
        int s;
        cin >> s;
        memset(park,false,sizeof park);
        int node[N];
        for(int i = 1;i <= s;i++){
            cin >> node[i];
            park[node[i]] = true;
        }
        for(int i = node[1];i <= node[s];i++){
            if(park[i])
                continue;
            for(int j = 1;j <= s;j++){
                if(!G[i][node[j]]){
                    G[i][node[j]] = true;
                    addedge(i,node[j]);
                    deg[node[j]]++;
                }
            }
        }
    }

    topsort();
    cout << ans;
    return 0; 
}