拓扑排序解决图中是否存在环路问题

算法

首先是前段时间网易游戏在线笔试的一道编程题：源代码编译

在leetcode上有一道几乎是一模一样的题目：207. Course Schedule

大意都是一个图中的某两个节点存在先后顺序，要求判断图中有没有环路。leetcode的提示说的也很明确：这是一个拓扑排序（Topological sort）的问题。

拓扑排序的定义：设有向图G中节点u和节点v之间存在有向边u->v，那么对节点排序的结果中，u始终在v的前面。

从定义中很容易得出，如果G中同时存在有向边u->v和v->u，也就是存在一个环路，那么u和v就无法确定谁在谁前面，也就是G无法被拓扑排序。因此，一个有向图能被拓扑排序的充要条件就是它是一个有向无环图。

数据结构教科书上有拓扑排序的典型算法，我摘录了一下网上对这个算法的总结：

1
维护一个入度为0的顶点的集合：
每次从该集合中取出(没有特殊的取出规则，随机取出也行，使用队列/栈也行，下同)一个顶点，将该顶点放入保存结果的List中。
紧接着循环遍历由该顶点引出的所有边，从图中移除这条边，同时获取该边的另外一个顶点，如果该顶点的入度在减去本条边之后为0，那么也将这个顶点放到入度为0的集合中。然后继续从集合中取出一个顶点…………
当集合为空之后，检查图中是否还存在任何边，如果存在的话，说明图中至少存在一条环路。不存在的话则返回结果List，此List中的顺序就是对图进行拓扑排序的结果。

对于leetcode的这道题，实现这个算法的代码如下：

public boolean canFinish(int numCourses, int[][] prerequisites) {

    // 用矩阵保存题目中的数据，matrix[i][j]表示i->j的有向边
    int[][] matrix = new int[numCourses][numCourses]; 
    // 记录每个顶点的入度
    int[] indegree = new int[numCourses];

    // 初始化
    for (int i=0; i<prerequisites.length; i++) {
        int ready = prerequisites[i][0];
        int pre = prerequisites[i][1];
        if (matrix[pre][ready] == 0)
            indegree[ready]++; // 避免重复计算相同的边
        matrix[pre][ready] = 1;
    }

    int count = 0; // 记录出队的顶点个数
    Queue<Integer> queue = new LinkedList();
    for (int i=0; i<indegree.length; i++) {
        if (indegree[i] == 0) queue.offer(i); // 入度为0的顶点入队
    }
    while (!queue.isEmpty()) {
        int course = queue.poll(); // 顶点course出队
        count++;
        for (int i=0; i<numCourses; i++) {
            if (matrix[course][i] != 0) { // 如果存在course->i的边
                if (--indegree[i] == 0) 
                    queue.offer(i);
                    // 顶点i的入度减一，如果入度变为0，顶点i入队
            }
        }
    }
    // 所有顶点均出队，说明排序完成，反之未完成，存在环路
    return count == numCourses;
}

上面的算法是基于BFS的，而用DFS同样能做拓扑排序，只不过和BFS正好相反，DFS的算法是维护一个出度为0的顶点集合。由于DFS使用了递归，需要用一段伪代码来描述一下：（来自维基百科）

1
L ← Empty list that will contain the sorted nodes
S ← Set of all nodes with no outgoing edges
for each node n in S do
    visit(n) 
function visit(node n)
    if n has not been visited yet then
        mark n as visited
        for each node m with an edge from m to n do
            visit(m)
        add n to L

根据这个思路，在BFS的代码上做一些改动可以得到DFS的代码：

public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[][] matrix = new int[numCourses][numCourses];
    boolean[] visited = new boolean[numCourses];
    for (int i=0; i<prerequisites.length; i++) {
        int ready = prerequisites[i][0];
        int pre = prerequisites[i][1];
        matrix[pre][ready] = 1;
    }
    for (int i=0; i<numCourses; i++) {
        if (!visit(matrix, visited, i)) return false;
    }
    return true;
}

private boolean visit(int[][] matrix, boolean[] visited, int course) {
    if (visited[course]) return false;
    else {
        visited[course] = true;
        for (int i=0; i<visited.length; i++) {
            if (matrix[i][course]!=0) {
                if (!visit(matrix, visited, i)) return false;
                // 如果存在i->course的边，对i递归调用visit方法
                // visited.length（numCourses）太大时会超时
            }
        }
        visited[course] = false;
        return true;
    }
}

然而上面这段代码在leetcode上是会超时的，可能是因为visit函数里的for循环体太长太暴力了，测试的时候numCourses=1000就不行了。可以考虑的优化方式是采用邻接表代替矩阵存储图的数据，这样的话i->course的边的数量可以确定为邻接表的长度，就不需要暴力搜索整个numCourses的长度了。