拓扑排序

Feb 28, 2021

百度百科

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

理解

就是将一个有向无环图的节点按着图的方向排序，也就是一个图上的边的两个顶点若为 u->v，则排序时 u 必须在 v 前面。

由此可以看出一个图的拓扑排序可能不止一种，可以自己举例试一下，加深理解。

实现方法

图的存储可以零用邻接矩阵或是邻接表，排序时，定义两个队列（queue）q1，q2，先遍历一次所有的节点求出各节点的入度，并找到入度为 0 的节点（即没有边指向的节点），将其放入 q1 中，接下来依次取出 q1 中的点，将其放入 q2 中，若该点有指向的点，将被指向的点入读减 1，若入度为零，则将其放入 q1 中，直至 q1 为空队列。

代码示例

queue<int> q;
//priority_queue<int,vector<int>,greater<int>>q;
//优先队列的话，会按照数值大小有顺序的输出
//此处为了理解，暂时就用简单队列
inttopo()
{
  for (inti = 1; i <= n; i++)
  {
    if (indegree[i] 0)
    {
      q.push(i);
    }
  }
  int temp;
  while (!q.empty())
  {
    temp = q.front(); //如果是优先队列，这里可以是top()
    printf("%d->", temp);
    q.pop();
    for (inti = 1; i <= n; i++) //遍历从temp出发的每一条边，入度--
    {
      if (maptemp)
      {
        indegree[i]--;
        if (indegree[i] 0)
          q.push(i);
      }
    }
  }
}