拓扑排序

所谓图的拓扑排序，就是让图中全部有向边都从左指向右，同时将所有顶点排列在一条水平线上。简单来说，就是有几门要学习的课程：$A,B,C,D,E,F$ ，要学某一门课时必须有先掌握的知识，例如，要学课程 $A$ ，必须得有 $C$ 这门课的基础，学 $C$ 必须有 $E$ 的基础，学 $B$ 也必须有 $E$ 的基础，等等条件。最后让你排列出一个合理的顺序来学习这几门课程。有多种方案的话就随意输出一组。

我们做的就是要找到入度为 $0$ 的点，也就是找到不需要有任何基础的课程，先学习这门课，再去学习以这门课为基础的其他课程。

讲解

编写一个程序，输出给定DAG $G$ 进行拓扑排序后的顶点顺序。

输入

$|V|$ $|E|$

$s_0$ $t_0$

$s_1$ $t_1$

$...$

其中 $|V|$ 、 $|E|$ 分别表示图G的顶点数和边数。

$s_i$ 、$t_i$ 表示图 $G$ 第 $i$ 条有向边连接的两个顶点的编号。

输出
按拓扑排序后的顺序输出图 $G$ 的顶点编号，每个顶点编号占一行。

我们可以将一张有向无环图转换成为将所有顶点排列在一条水平直线。这样只要从左向右按顺序执行工作，就能保证执行当前工作时已经完成所有准备工作。

应用dfs或bfs都能较简单的实现拓扑排序。

• bfs方法(伪代码)

topologicalSort()
{
    将所有节点的color[u]设置为WHITE
    //设置所有节点u的入度indeg[u]
    for u 从 0 至 |V| - 1
        if indeg[u] == 0 && color[u] == WHITE
            bfs(u)
}
bfs(ints)
{
    Q.push(s)
    color[s] = GRAY
    while Q 不为空
        u = Q.dequeue()

        out.push_back(u)  //将入度为0的顶点加入链表

        for 与u相邻的节点v
            indeg[v]--
            if indeg[v] == 0 && color[v] == WHITE
            color[v] = GRAY
            Q.dequeue(v)
}

上述算法根据广度优先搜索的顺序依次访问入度为0的顶点，并将访问过的顶点添加至链表末尾。

该算法将访问过的顶点u视为“已结束”，同时将下一节点v（从u出发的边指向的顶点）的入度减1。这一操作相当于删除边。不断地删除可以使v的入度逐渐降为0，此时我们便可以访问顶点v，然后将v加入链表。

• dfs方法(伪代码)

topologicalSort()
    将所有节点的color[u] 设置为 WHITE

    for s从0至|V| - 1
    if color[s] == WHITE
        dfs(s)
dfs(u)
    for 与u相邻的节点v
        if color[v] == WHITE
            dfs(v)
    out.push_front(u)  //将访问结束的顶点逆向加入至链表

上述算法通过深度优先搜索访问顶点，并把访问完的点添加至链表开头。这里要注意，由于深度优先搜索是逆向确定各顶点的拓扑顺序，因此顶点是添加至链表开头的。

参考代码

• bfs实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<cstdlib>
#include<functional>
#include<climits>
#include<cctype>
#include<iomanip>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define mod 1e9+7
#define clr(a,x) memset(a,x,sizeof(a))
const double eps = 1e-6;
const int MAX = 100000;

vector<int> G[MAX];
list<int> out;
bool V[MAX];
int N;
int indeg[MAX];

void bfs(int s)
{
    queue<int> q;
    q.push(s);
    v[s] = true;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        out.push_back(u);
        for(int i=0;i<G[u].size();i++)
        {
            int v = G[u][i];
            indeg[v]--;
            if(indeg[v] == 0 && !V[v])
            {
                V[v] = true;
                q.push(v);
            }
        }
    }
}

void tsort()
{
    for(int i=0;i<N;i++)
    {
        indeg[i]=0;
    }
    for(int u=0;u<N;u++)
    {
        for(int i=0;i<G[u].size();i++)
        {
            int v = G[u][i];
            indeg[v]++;
        }
    }
    for(int u=0;u<N;u++)
        if(indeg[u] == 0 && !V[u])
            bfs(u);
    for(list<int>::iterator it = out.begin(); it != out.end();it++)
    {
        cout<< *it <<end;
    }
}

int main()
{
    int s,t,M;
    cin>>N>>M;
    for(int i=0;i<N;i++)
    {
        V[i] = flase;
    }
    for(int i=0;i<M:i++)
    {
        cin>>s>>t;
        G.push_back(t);
    }
    tsort();

    return 0;
}

• dfs实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<cstdlib>
#include<functional>
#include<climits>
#include<cctype>
#include<iomanip>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define mod 1e9+7
#define clr(a,x) memset(a,x,sizeof(a))
const double eps = 1e-6;
const int MAX = 100000;
vector<int> G[MAX];
list<int> out;
bool V[MAX];
int N;

void dfs(int u)
{
    V[u] = true;
    for(int i=0;i<G[u].size();i++)
    {
        int v = G[u][i];
        if(!V[v])
            dfs(v);
    }
    out.push_front(u);
}

int main()
{
    int s,t,M;
    cin>>N>>M;
    for(int i=0;i<N;i++)
    {
        V[i] = false;
    }
    for(int i=0;i<M;i++)
    {
        cin>>s>>t;
        G[s].push_back(t);
    }
    for(int i=0;i<N;i++)
    {
        if(!V[i])
            dfs(i);
    }
    for(list<int>::iterator it = out.begin();it!=out.end();it++)
    {
        cout<< *it <<endl;
    }
    return 0;
}

例题

题目

Description

有 $N$ 个比赛队 $(1 \leq N \leq 500)$ ，编号依次为 $1$，$2$ ，$3$ ，$...$ ，$N$ 进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即 $P_1$ 赢 $P_2$ ，用 $P_1$，$P_2$ 表示，排名时$P_1$ 在 $P_2$ 之前。现在请你编程序确定排名。

Input

输入有若干组，每组中的第一行为二个数 $N$ $(1 \leq N \leq 500)$ ，$M$ ；其中 $N$ 表示队伍的个数，$M$ 表示接着有 $M$ 行的输入数据。接下来的 $M$ 行数据中，每行也有两个整数 $P_1$，$P_2$ 表示即 $P_1$ 队赢了 $P_2$ 队。

Output

给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。

其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。

Sample Input

4 3
1 2
2 3
4 3

Sample Output

1 2 4 3

分析

这是一道简单的拓扑排序问题，完全可以套用上面讲解的知识来完成它。给出的代码是用bfs的方法实现的，具体请看代码。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<cstdlib>
#include<functional>
#include<climits>
#include<cctype>
#include<iomanip>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define mod 1e9+7
#define clr(a,x) memset(a,x,sizeof(a))
const double eps = 1e-6;
const int maxn=505;
int indegree[maxn];
vector <int> v[maxn];
int n,m;
queue<int> ans;
bool suc=true;
bool isfirst=true;
void output()
{
    while(!ans.empty())
    {
        int t=ans.front();
        ans.pop();
        if(isfirst)
        {
            cout<<t;
            isfirst=false;
        }
        else
            cout<<" "<<t;
    }
}
void topsort()
{
    queue <int> q;
    while(1)
    {
        for(int i=1;i<=n;i++)
        {
            if(indegree[i]==0)
            {
                q.push(i);
                ans.push(i);
                indegree[i]=-1;
                break;
            }
        }
        if(q.empty())
        {
            break;
        }
        while(!q.empty())
        {
            int t=q.front();
            q.pop();
            for(int i=0;i<v[t].size();i++)
            {
                int tt=v[t][i];
                if(indegree[tt]==-1)
                {
                    suc=false;
                    break;
                }
                else
                    indegree[tt]--;
            }
            v[t].clear();
            if(!suc)
                break;
        }
        if(!suc)
            break;
        output();
    }
    if(suc&&ans.size()!=n)
        suc=false;
}
int main()
{
    while(cin>>n>>m)
    {
        clr(indegree,0);
        suc=true;
        isfirst=true;
        for(int i=0;i<m;i++)
        {
            int a,b;
            cin>>a>>b;
            indegree[b]++;
            v[a].push_back(b);
        }
        topsort();
        cout<<endl;
    }
    return 0;
}