三色标记法 判断有向图是否有环

• 判断图是否有环，是一个技术性的问题，当一个图规定了起点的时候，我们只需设置一个visited数组（初始值为False），当接下来访问到的结点i是visited[i]=True的时候，我们就可以说存在一个环了，这样的话，时间复杂度就是o(n)
• 但是，如果图并有规定从哪一个顶点开始，那么我们应该如何判断这个图中是否存在环？由于没有规定是从哪一个点作为遍历的开始，所以要是采用上面的思路进行的话，就需要考虑从每一个点作为起点的情况，那么这样的话，时间复杂度就会来到o(n^2),那么应该怎么办？

下面介绍三色标记法，也就是将结点分为，未被访问、正在访问、已经访问过，这三种情况

三色标记法

• 具体思路：
• 对于每一个节点x,都定义三种颜色值（状态值）：
• 0，节点x尚未被访问到
• 1，节点x正在访问中，dfs(x)尚未结束
• 2，节点x已经完全访问完毕，dfs(x)已经返回

注意：只使用两种状态是不能处理是否存在环的

我们所说的，节点x正在访问中，是说我们正在递归处理节点x以及它的后续节点，dfs(x)尚未结束

• 时间复杂度：每个节点只会被访问一次，每一条边也会被访问一次，所以时间复杂度是o(N+E)

• 思路分析：直接套用三色标记法即可

Python思路

class Solution:def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:g = [[] for _ in range(numCourses)]for a, b in prerequisites:g[b].append(a)colors = [0] * numCourses# 返回 True 表示找到了环def dfs(x: int) -> bool:colors[x] = 1  # x 正在访问中for y in g[x]:if colors[y] == 1 or colors[y] == 0 and dfs(y):return True  # 找到了环colors[x] = 2  # x 完全访问完毕return False  # 没有找到环for i, c in enumerate(colors):if c == 0 and dfs(i):return False  # 有环return True  # 没有环

C++思路

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<vector<int>> g(numCourses);for (auto& p : prerequisites) {g[p[1]].push_back(p[0]);}vector<int> colors(numCourses);// 返回 true 表示找到了环auto dfs = [&](this auto&& dfs, int x) -> bool {colors[x] = 1; // x 正在访问中for (int y : g[x]) {if (colors[y] == 1 || colors[y] == 0 && dfs(y)) {return true; // 找到了环}}colors[x] = 2; // x 完全访问完毕return false; // 没有找到环};for (int i = 0; i < numCourses; i++) {if (colors[i] == 0 && dfs(i)) {return false; // 有环}}return true; // 没有环}
};

• 思路分析：

python代码

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<vector<int>> g(numCourses);for (auto p: prerequisites){g[p[1]].push_back(p[0]);}vector<int> colors(numCourses);auto dfs = [&](this auto && dfs,int x) -> bool{colors[x] = 1;for (int y : g[x]){if (colors[y] == 1 || colors[y] == 0 && dfs(y)){return true;}}colors[x] = 2;return false;};for (int i = 0; i < numCourses; i++){if (colors[i] == 0 && dfs(i)){return false;}}return true;}
};