拓扑排序

「拓扑排序」是专门应用于有向图的算法，它能够顺带检测有向图中是否存在环。注意：「拓扑排序」的结果不唯一。如果且仅当图形没有定向循环，即如果它是有向无环图（DAG），则拓扑排序是可能的。任何 DAG 具有至少一个拓扑排序，存在算法用于在线性时间内构建任何 DAG 的拓扑排序。

对于拓扑排序类型的问题，可以采用BFS和DFS来解决。BFS的解法很经典，本文只介绍BFS，不对DFS进行扩展(其实是我对拓扑排序的DFS解决不太熟~~~)。

以leetcode 207 课程表问题为例，算法流程分为以下步骤：

1、使用邻接表保存有向图
2、统计图中每个节点的入度，生成入度数组
3、使用队列存储所有入度为0的节点
4、当队列非空时，依次将队首节点出队，并更新该节点对应的邻接表，将其邻接表上的节点的入度-1，同时将新的入度为0的节点入队
5、如果整个图是有向无环图，那么所有节点可以完成拓扑排序(即所有节点入队并出队)，否则，最终将有节点的入度不为0，不能完成拓扑排序

时间复杂度 O(N + M)：遍历一个图需要访问所有节点和所有临边，N 和 M 分别为节点数量和临边数量；空间复杂度 O(N + M)：为建立邻接表所需额外空间。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] in = new int[numCourses];
        List<List<Integer>> list = new ArrayList<>();
        for (int i=0; i<numCourses; i++) {
            list.add(new ArrayList<>());
        }
        for (int[] prerequisite: prerequisites){
            in[prerequisite[0]]++;
            list.get(prerequisite[1]).add(prerequisite[0]);
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i=0; i<numCourses; i++) {
            if (in[i] == 0) {
                queue.offer(i);
            }
        }
        int count = 0;
        while (!queue.isEmpty()) {
            count++;
            int temp = queue.poll();
            for (int i : list.get(temp)) {
                in[i]--;
                if (in[i] == 0) {
                    queue.offer(i);
                }
            }
        }
        return count == numCourses;
    }
}

拓扑排序

Post Directory