1、介绍

拓扑排序主要应用于有向无环图，所谓的有向无环图指的是，图中没有环。如图：

有向无环图

拓扑排序是一个有向无环图的所有顶点的线性序列。且该序列必须满足下面两个条件：

1、每个顶点出现且只出现一次。

2、若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

2、拓扑排序的方法

一种比较常用的方法：

1、从 DAG 图中选择一个没有前驱（即入度为0）的顶点并输出。

2、从图中删除该顶点和所有以它为起点的有向边。

3、重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

方法

3、拓扑排序的应用

拓扑排序通常用来“排序”具有依赖关系的任务。

比如，如果用一个DAG图来表示一个工程，其中每个顶点表示工程中的一个任务，用有向边表示在做任务 B 之前必须先完成任务 A。故在这个工程中，任意两个任务要么具有确定的先后关系，要么是没有关系，绝对不存在互相矛盾的关系（即环路）。

引申到任务那块，任务如果有相互依赖，是不是也是那种有向无环图？

4、代码实现


int topo()
{
    queue<int>q;

    // 将所有入度为0的顶点加入
    for(inti=1;i<=n;i++)
    {
        if(indegree[i]==0)
        {
            q.push(i);
        }
    }
 
    int temp;
    while(!q.empty())
    {
        temp=q.pop();
        for(inti=1;i<=n;i++)//遍历从temp出发的每一条边，入度--
        {
            if(map[temp][i])
            {
                indegree[i]--;
                if(indegree[i]==0)q.push(i);
            }
        }
    }
}