Topological sort
2021-01-06 本文已影响0人
Wilbur_
这个听起来是个非常高深的算法,但实际上只是BFS的另一种应用罢了
核心思想就是通过图中最外层的节点往里走,一层一层递进。这里有个indegree的概念(入度?)indegree就是一个描述“层”的数组。也就是说最外层的indegree就是0,因为indegree代表的就是有多少个指向该节点的节点。所以叫indegree. 那么怎么找到indegree呢?通过courseSchedule这道题,你就是遍历所有的prerequisite的数组,然后每次遇到prerequisite的课,就把它对应的indegree加一。
for (int i = 0; i < prerequisite.length; i++) {
int start = prerequisite[i][1], end = prerequisite[i][0];
//注意这里prerequisite 的结构,[0,1]代表1的先修课是0,所以start 是prerequisite[i][0], end 是prerequisite[i][1];
graph.putIfAbsent(start, new ArrayList<>());
graph.get(start).add(end); //把start之后的课程计入到它对应的队列中
indegree[end]++; //增加indegree
}
做完上面这步之后你就可以安心用BFS来遍历所有的外围节点了。同样用Queue,然后把indegree为0的节点加入queue中,开始遍历(跟正常的level order traversal一样)
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < indegree.length; i++) {
if (indegree[i] == 0) q.add(i);
}
int count = 0; //这个count就是为了记录有多少个indegree为0,然后比较总共课程数量,即可知道你是否能够上完全部的课(这张图有没有环,或者说是不是一个DAG,有向无环图)
while (!q.isEmpty()) {
int cur = q.poll();
count++;
for (int nei : graph.getOrDefault(cur, new ArrayList<>()) {
if (--indegree[nei] == 0)
q.add(nei);
}
}
return count == numsCourses;
下面是整段代码:
public boolean canFinish(int numCourses, int[][] prerequisites) {
Map<Integer, List<Integer>> graph = new HashMap<>();
int[] indegree = new int[numCourses];
for (int i = 0; i < prerequisites.length; i++) {
int end = prerequisites[i][0], start = prerequisites[i][1];
graph.putIfAbsent(start, new ArrayList<>());
graph.get(start).add(end);
indegree[end]++;
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) q.add(i);
}
int count = 0;
while(!q.isEmpty()) {
int cur = q.poll();
count++;
for (int next : graph.getOrDefault(cur, new ArrayList<>()))
if (--indegree[next] == 0)
q.add(next);
}
return count == numCourses;
}
时空复杂度
O(N+E) N就是有多少节课,你遍历了至少3遍,E就是有多少prerequisite
空间复杂度也是O(N+E) 因为你要用map或者ArrayList来存起始课和之后的关系。