环检测和拓扑排序的关系很密切：
- 它们的基础都是图的遍历。
- 拓扑排序依赖于环检测算法，做拓扑排序需要先检测图中是否存在环，有环图是无法拓扑排序的。
环检测
什么是环检测算法？
环检测算法就是检测一个图中是否存在环的算法。
环检测算法有什么用？
可以用来判断是否存在循环依赖，207.课程表是一道运用环检测算法的典型题目。
dfs实现
理解以下几个点：
visited 和 onPath 数组各自的作用和区别：visited 数组的作用是标记节点的访问情况，避免重复访问同一节点，它是 dfs 的基础辅助数组；只需要在进入每个节点时，更新一次相应的访问信息即可，不需要回溯。onPath 是用来判断节点是否在当前路径中的，而遍历的过程中，当一个路径走到头之后，是需要回过头去找下一条路径的，这个时候就需要回溯，将不在路径中的节点信息抹掉。
信息流转过程：依赖表——>构建邻接表——>dfs环检测，更新onPath、visited、hasSycle——>根据hasSycle值，返回结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| class Solution {
private boolean hasSycle = false;
private boolean[] onPath;
private boolean[] visited;
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] graph = buildGraph(numCourses, prerequisites);
onPath = new boolean[numCourses];
visited = new boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
if (!visited[i]) {
ringDetect(graph, i);
if (hasSycle) {
break;
}
}
}
if (hasSycle) {
return false;
} else {
return true;
}
}
private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
List<Integer>[] graph = new ArrayList[numCourses];
for (int i = 0; i < numCourses; i++) {
graph[i] = new ArrayList<Integer>();
}
for (int i = 0; i < prerequisites.length; i++) {
int from = prerequisites[i][1];
int to = prerequisites[i][0];
graph[from].add(to);
}
return graph;
}
private void ringDetect(List<Integer>[] graph, int node) {
if (onPath[node]) {
hasSycle = true;
return;
}
if (visited[node]) {
return;
}
visited[node] = true;
onPath[node] = true;
for (int nextNode : graph[node]) {
ringDetect(graph, nextNode);
if (hasSycle) {
return;
}
}
onPath[node] = false;
}
}
|
bfs实现
理解几个点：
inDegree数组是如何控制遍历顺序的：初始化inDegree数组——>遍历inDegree数组，将入度为零的课程入队，作为起始课程——>每遍历一个课程，将它的后续课程的入度减一，相当于这门课程的先修课程又完成了一门——>减一操作之后判断这门课程的入度是否已经为0，如果为0，则入队。通过这样的方式，可以保证，访问一门课程之前，这门课程的先修课一定都完成了。- 为什么用这种方法可以判断图中是否有环：判断是否存在环借助了
count变量，每当从队列中获取一个课程时，count加一。通过这种方式统计已经修过的课程，如果最终遍历完了所有节点，自然就不存在环，count会等于课程数；而如果存在环，成环的那几门课程会互相增加一个入度，导致这几个节点不会被访问，最终count会小于课程数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] inDegree = new int[numCourses];
List<Integer>[] graph = new ArrayList[numCourses];
for (int i = 0; i < numCourses; i++) {
graph[i] = new ArrayList<Integer>();
}
for (int i = 0; i < prerequisites.length; i++) {
int from = prerequisites[i][1];
int to = prerequisites[i][0];
graph[from].add(to);
inDegree[to]++;
}
Queue<Integer> que = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
que.offer(i);
}
}
int count = 0;
while(!que.isEmpty()) {
count++;
int course = que.poll();
for (int nextCourse : graph[course]) {
inDegree[nextCourse]--;
if (inDegree[nextCourse] == 0) {
que.offer(nextCourse);
}
}
}
if (count == numCourses) {
return true;
} else {
return false;
}
}
}
|
