1.拓扑排序简介

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。(百度百科)

2.拓扑排序的过程

首先找到图中入度为0的点，删除它，并使被它连接点的入度减一。循环以上过程。拓扑排序仅针对无环有向图。过程其实很简单，所以不提供伪代码。

3.例题（POJ2367）

• 题意
  给出一个有向无环图求拓扑序列。
• 实现

#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define M 1000000007
using namespace std;
typedef long long LL;
const int maxn = 105;

int in[maxn]; //记录入度
int adj[maxn][maxn]; //邻接矩阵
int ans[maxn]; //存答案
int n;

void init()
{
    memset(in,0,sizeof(in));
    memset(adj,0,sizeof(adj));
}

void topo_sort() //拓扑排序
{
    int now; //要处理的点
    for(int i = 1;i <= n;++i)
    {
        for(int j = 1;j <= n;++j) //找一个入度为0的点
            if(in[j] == 0)
            {
                now = j;
                break;
            }
        in[now] = -INF; //标记为无入度以免二次处理
        ans[i] = now;
        for(int j = 1;j <= n;++j)
            if(adj[now][j])
            {
                adj[now][j] = 0; //删除路径
                in[j]--; //入度减一
            }
    }
}

int main()
{
    while(~scanf("%d", &n))
    {
        init();
        int next;
        for(int i = 1;i <= n;++i)
        {
            while(scanf("%d", &next)) //输入并记录入度
            {
                if(next == 0)
                        break;
                adj[i][next] = 1;
                in[next]++;
            }
        }
        topo_sort();
        printf("%d", ans[1]);
        for(int i = 2;i <= n;++i)
            printf(" %d", ans[i]);
        printf("\n");
    }

    return 0;
}

总提纲：《数据结构》期末提纲小结