拓扑排序

概述

拓扑排序，我的理解就是：有向图中所有节点的一种排列，这个排列需要满足下面两个条件：

• 序列包含图中所有节点，且每个节点只出现一次；
• 若A在序列中排在B的前面，则图中不存在从B到A的路径。

从拓扑排序的定义，我们不难推断出下面的结论：

• 当且仅当图中没有环时，即有向无环图，才有拓扑排序；
• 任何有向无环图，至少有一个拓扑排序。

对于有向无环图，有两种经典算法，可以求出它的拓扑排序：卡恩算法和深度优先搜索。其中卡恩算法可以理解成广度优先搜索，下面详细介绍下这两种算法的实现。

经典算法

卡恩算法

卡恩在1962年提出了该算法，很好理解，类似于广度优先搜索，大概思路如下：

假设D为存储了所有节点的入度，用集合S存储所有入度为0的节点，L用来存储所有排好序的列表。首先将S中所有节点添加到L的尾部，同时更新和S中节点相关联的其他节点的入度，然后再将更新后入度为0的节点加入S中，重复上述步骤。

下面是来自维基百科的伪代码。

L ← 包含已排序的元素的列表，目前为空
S ← 入度为零的节点的集合
当 S 非空时：
    将节点n从S移走
    将n加到L尾部
    选出任意起点为n的边e = (n,m)，移除e。如m没有其它入边，则将m加入S。
    重复上一步。
如图中有剩余的边则：
    return error   (图中至少有一个环)
否则： 
    return L   (L为图的拓扑排序)

光看思路可能不好理解，下图展示了卡恩算法的大致流程：

看到这里，我们已经清楚了卡恩算法的思想和具体实现细节，下面我用java来重述一下如何实现卡恩算法。

//节点入度数组，大小为节点数量
int[] degree = new int[n];
//类似邻接矩阵，用来记录图中的边，比如节点1指向2和4，可以记录为{1:[2,4]}。也可以用二维数组来记录
HashMap<Integer, List<Integer>> edges = new HashMap<>();
//记录入度为0的节点，这里用队列
Queue<Integer> queue = new LinkedList<>();
for(int i = 0; i < n; ++i){
    //所有入度为0的节点放到队列中
    if(degree[i] == 0)
        queue.offer(i);
}
int count = 0;//记录节点数量，可以用来判断图是否有环
int[] topo = new int[n];//记录拓扑排序序列
while(!queue.isEmpty()){
    int node = queue.poll();
    topo[count++] = node;
    if(edges.containsKey(node)){
        //去掉节点node，更新所有和node相邻的节点的入度
        for(Integer item : map.get(node)){
            degree[item]--;
            //如果节点入度变为0，将它加入队列中
            if(degree[item] == 0)
                queue.offer(item);
        }
    }
}

深度优先搜索

另一种拓扑排序的方法是深度优先搜索，卡恩算法是从前往后依次确定拓扑排序中每个节点，深度优先算法则相反，它是从后往前确定序列中每个节点的，也就是先找到那些没有后继节点的节点，把它们放到序列尾部，然后继续搜索。下面是维基百科中给出的伪代码：

L ← 包含已排序的元素的列表，目前为空
当图中存在未永久标记的节点时：
    选出任何未永久标记的节点n
    visit(n)
function visit(节点 n)
    如n已有永久标记：
        return
    如n已有临时标记：
        stop   (不是定向无环图)
    将n临时标记
    选出以n为起点的边(n,m)，visit(m)
    重复上一步
    去掉n的临时标记
    将n永久标记
    将n加到L的起始 

上面的动图展示了DFS的标记过程，下面我们用Java代码进行简单实现：

//用一个map存储边信息
Map<Integer, List<Integer>> map = new HashMap<>();
//用flag数组进行深度搜索，0表示未访问，1表示dfs过程的临时标记，2表示节点以加入拓扑序列
int[] flag = new int[n];
//记录拓扑序列
int[] topo = new int[n];
for(int i = 0; i < n; ++i){
	if(flag[i] == 0)
        dfs(i, flag, map);
}

public void dfs(int node, int[] flag, Map<Integer, List<Integer>> map){
    //节点已经加入拓扑序列
    if(flag[node] == 2)
        return;
   	flag[node] = 1;
    if(map.containsKey(node)){
        for(int item : map.get(node)){
            //存在环，退出
            if(flag[item] == 1)
                return;
            dfs(item, flag, map);
        }
    }
    //节点加入拓扑序列中
    flag[node] = 2;
    topo[count++] = node;
}

拓扑排序实战

拓扑排序相关的常见问题有一下几种：

1. 给定无向图，让你判断图中是否有环，判断拓扑序列中元素个数是否等于节点个数。

   • 207. 课程表

2. 给定无向图，让你输出任意一种拓扑序列，卡恩算法或者深度优先遍历即可。

   • 210. 课程表 II

3. 给定无向图，问a节点是否是b节点的先序（DFS的话用逆邻接矩阵比较方便，问题转化成a是否在b的先序节点集合中）。

   BFS需要额外加一个Map<Integer, Set<Integer>> map记录每个节点的前置节点集合。

   • 1462. 课程表 IV

打赏