有向图的环检测
https://labuladong.github.io/algo/2/19/35/https://mp.weixin.qq.com/s/xHmzLa4LtxOHEro0g3rBZw
Version 1: BFS+Adjacency List (Leetcode的207)
BFS的解法,用邻接表表示图(这里的邻接表用List<List<>>表示,而不是List<HashSet<>>,因为Testcase中二维数组有重复的所以用List而不用Set,对于重复的边,它在邻接表中村了两份,同时计算入度时也算了两次)一位数组indegree来表示每个顶点的入度。
我们开始先根据输入来建立这个有向图,同时将入度数组indegree也初始化好。
然后我们定义一个queue变量,将所有入度为0的点放入队列中,
然后开始遍历队列,从graph里遍历其连接的点,每到达一个新节点,将其入度减一,如果此时该点入度为0,则放入队列末尾。
直到遍历完队列中所有的值,若此时还有节点的入度不为0,则说明环存在,返回false,反之则返回true.
---------------------------------------------------------------------
其实 BFS 算法借助 indegree
数组记录每个节点的「入度」,也可以实现这两个算法。不熟悉 BFS 算法的读者可阅读前文 BFS 算法核心框架。
所谓「出度」和「入度」是「有向图」中的概念,很直观:如果一个节点x
有a
条边指向别的节点,同时被b
条边所指,则称节点x
的出度为a
,入度为b
。
先说环检测算法,直接看 BFS 的解法代码:
// 主函数
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 建图,有向边代表「被依赖」关系
List<Integer>[] graph = buildGraph(numCourses, prerequisites);
// 构建入度数组
int[] indgree = new int[numCourses];
for (int[] edge : prerequisites) {
int from = edge[1], to = edge[0];
// 节点 to 的入度加一
indgree[to]++;
}
// 根据入度初始化队列中的节点
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indgree[i] == 0) {
// 节点 i 没有入度,即没有依赖的节点
// 可以作为拓扑排序的起点,加入队列
q.offer(i);
}
}
// 记录遍历的节点个数
int count = 0;
// 开始执行 BFS 循环
while (!q.isEmpty()) {
// 弹出节点 cur,并将它指向的节点的入度减一
int cur = q.poll();
count++;
for (int next : graph[cur]) {
indgree[next]--;
if (indgree[next] == 0) {
// 如果入度变为 0,说明 next 依赖的节点都已被遍历
q.offer(next);
}
}
}
// 如果所有节点都被遍历过,说明不成环
return count == numCourses;
}
// 建图函数
List<Integer>[] buildGraph(int n, int[][] edges) {
// 见前文
}
我先总结下这段 BFS 算法的思路:
1、构建邻接表,和之前一样,边的方向表示「被依赖」关系。
2、构建一个 indegree
数组记录每个节点的入度,即 indegree[i]
记录节点 i
的入度。
3、对 BFS 队列进行初始化,将入度为 0 的节点首先装入队列。
4、开始执行 BFS 循环,不断弹出队列中的节点,减少相邻节点的入度,并将入度变为 0 的节点加入队列。
5、如果最终所有节点都被遍历过(count
等于节点数),则说明不存在环,反之则说明存在环。
我画个图你就容易理解了,比如下面这幅图,节点中的数字代表该节点的入度:
队列进行初始化后,入度为 0 的节点首先被加入队列:
开始执行 BFS 循环,从队列中弹出一个节点,减少相邻节点的入度,同时将新产生的入度为 0 的节点加入队列:
继续从队列弹出节点,并减少相邻节点的入度,这一次没有新产生的入度为 0 的节点:
继续从队列弹出节点,并减少相邻节点的入度,同时将新产生的入度为 0 的节点加入队列:
继续弹出节点,直到队列为空:
这时候,所有节点都被遍历过一遍,也就说明图中不存在环。
反过来说,如果按照上述逻辑执行 BFS 算法,存在节点没有被遍历,则说明成环。
比如下面这种情况,队列中最初只有一个入度为 0 的节点:
当弹出这个节点并减小相邻节点的入度之后队列为空,但并没有产生新的入度为 0 的节点加入队列,所以 BFS 算法终止:
你看到了,如果存在节点没有被遍历,那么说明图中存在环,现在回头去看 BFS 的代码,你应该就很容易理解其中的逻辑了。
Version 2: DFS+Adjacency List (Leetcode的207)
用visited 和onPath数组来做图的DFS。
// 记录一次递归堆栈中的节点
boolean[] onPath;
// 记录遍历过的节点,防止走回头路
boolean[] visited;
// 记录图中是否有环
boolean hasCycle = false;
boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] graph = buildGraph(numCourses, prerequisites);
visited = new boolean[numCourses];
onPath = new boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
// 遍历图中的所有节点
traverse(graph, i);
}
// 只要没有循环依赖可以完成所有课程
return !hasCycle;
}
void traverse(List<Integer>[] graph, int s) {
if (onPath[s]) {
// 出现环
hasCycle = true;
}
if (visited[s] || hasCycle) {
// 如果已经找到了环,也不用再遍历了
return;
}
// 前序代码位置
visited[s] = true;
onPath[s] = true;
for (int t : graph[s]) {
traverse(graph, t);
}
// 后序代码位置
onPath[s] = false;
}
List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
// 代码见前文
}
不过如果出题人继续恶心你,让你不仅要判断是否存在环,还要返回这个环具体有哪些节点,怎么办?
你可能说,onPath
里面为 true 的索引,不就是组成环的节点编号吗?
不是的,假设下图中绿色的节点是递归的路径,它们在 onPath
中的值都是 true,但显然成环的节点只是其中的一部分:
Last updated
Was this helpful?