拓扑排序

概念：

  • 在一个有向图中，对所有节点排序后，对于每一条边都是前面指向后面，没有由后面指向前面的边，则称新的序列为有向图的拓扑排序。若有向图存在环，必然没有拓扑排序；若有向图无环，则必然存在一个拓扑排序。
  • 如果一个图是可以拓扑排序的，则称此图为拓扑图 == 有向无环图(DAG)

算法实现：

  • 将所有入读为0的点入队
    1
    2
    3
    4
    5
    6
    7
    8
    9
    while (q 非空)
    {
      t <- q的头节点
      for t 的所有出边 t -> j
      {
          -- d[j];
          if (d[j] == 0) q <- j;
      }
    }

算法模板如下：

如果求字典序最小的拓扑排序，将 队列换成优先队列即可。

当前队列的元素为 度数为0 的点，当前序列中的点一定为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void topsort()
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++ )
        if(!d[i])
            q[ ++ tt] = i;
    
    while(hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if( -- d[j] == 0)
                q[ ++ tt] = j;
        }
    }
}