Leetcode 210 Course Schedule 拓扑排序
题目表述
There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
Example 1:
Input: 2, [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1] .
Example 2:
Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .
解题分析
这道题是一道典型的拓扑排序的问题，我先后在vmware, facebook和apple的三次面试中遇到过这道题，是一道实打实的高频面试题。拓扑排序是图的经典问题，解决拓扑问题的思路大致有两种，即BFS和DFS。
Represent Graph
这是leetcode中常见的一个问题，即如何重新表述一个图结构。对于无向图而言，图数据结构的两种常见表述形式是，
1. Adjacency matrix 邻接矩阵： 对于一个N结点的图而言，构造一个N*N的矩阵，当图中包含边(i,j)时，M[i][j] = 1；否则 M[i][j] = 0;
private int[][] buildAdjacencyMatrix(int N, int[][] edges){
int[][] adjancencyMatrix = new int[N][N];
for (int[] edge:edges){
adjancencyMatrix[edge[0]][edge[1]] = 1;
adjancencyMatrix[edge[1]][edge[0]] = 1;
}
return adjancencyMatrix;
}
- Adjacency List 邻接链表：对于一个N结点的图而言，构造N个链表，当图中包含边(i,j)时，j在i指向的链表中。
private List<List<Integer>> buildAdjancencyList(int N, int[][] edges){
List<List<Integer>> AdjancencyList = new ArrayList<>();
for (int i=0;i<N;i++) AdjancencyList.add(new ArrayList<>);
for (int[] edge:edges){
adjancencyList.get(edge[0]).add(edge[1]);
adjancencyList.get(edge[1]).add(edge[0]);
}
}
对于有向图而言，需要进一步考虑边的指向性，而不仅仅构造对称的数据结构。显然本题中的拓扑关系存在方向性，我们构造的是一个有向图。并且，这道题不保证构造有向无环图，一旦构成有环图，则返回一个空列表作为答案。
广度优先搜索
所谓广度优先搜索，就是首先找到没有任何依赖关系的起始点，随后将起始点从图中移除后，再计算新的起始点。
为此，我们需要维护如下的数据结构，
1. edges: 一个采用邻接矩阵存储的图数据结构
2. InDegreeMap : 即各个节点的入度计量。
3. pointsQueue : 待更新的起始点列表
4. result: 结果列表
在本题中，BFS的算法复杂度为N*N (N为图中的节点数量)。以下为本题的AC解。
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] indegrees = new int[numCourses];
int[][] edges = new int[numCourses][numCourses];
int[] result = new int[numCourses];
int count = 0;
for (int[] pre:prerequisites){
indegrees[pre[0]] = indegrees[pre[0]]+1;
edges[pre[1]][pre[0]] = 1;
}
List<Integer> queue = new ArrayList<>();
for (int i=0;i<numCourses;i++){
//System.out.printf("Course:%d indegree:%d\n",i,indegrees[i]);
if (indegrees[i]==0) {
queue.add(i);
indegrees[i] = -1;
}
}
if (queue.size()==0) return new int[0];
while (count<numCourses&&!queue.isEmpty()){
int number = queue.size();
//System.out.printf("------------------\n");
for (int i=0;i<number;i++){
int course = queue.remove(0);
//System.out.printf("Course:%d Count:%d\n",course,count);
result[count] = course;
count++;
for (int j=0;j<numCourses;j++){
if (edges[course][j]==1){
indegrees[j]--;
//System.out.printf("Update Course:%d Indegree:%d\n",j,indegrees[j]);
}
}
}
for (int j=0;j<numCourses;j++){
if (indegrees[j]==0) {
queue.add(j);
indegrees[j]=-1;
}
}
}
if (queue.isEmpty()&&count<numCourses) return new int[0];
return result;
}
}
采用上述方法通过leetcode检测，效率高于29%的提交。
深度优先搜索
广度优先搜索是从前向后的，首先找到所有任务起始的结点，随后逐渐向后递推；深度优先搜索则是从任意一个course出发，逐步向前追溯,直到到达最开始的任务。
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; ++i)
graph.add(new ArrayList<Integer>());
for (int i = 0; i < prerequisites.length; ++i) {
int course = prerequisites[i][0];
int prerequisite = prerequisites[i][1];
graph.get(course).add(prerequisite);
}
int[] visited = new int[numCourses];
List<Integer> ans = new ArrayList<Integer>();
Integer index = numCourses;
for (int i = 0; i < numCourses; ++i)
if (dfs(i, graph, visited, ans)) return new int[0];
return ans.stream().mapToInt(i->i).toArray();
}
private boolean dfs(int curr, ArrayList<ArrayList<Integer>> graph, int[] visited, List<Integer> ans) {
if (visited[curr] == 1) return true;
if (visited[curr] == 2) return false;
visited[curr] = 1;
for (int next : graph.get(curr))
if (dfs(next, graph, visited, ans)) return true;
visited[curr] = 2;
ans.add(curr);
return false;
}
}