有向图检测环（DFS思路分析）
有向图检测环（DFS思路分析）
一 引言
上一篇博客简要说明了无向图用DFS检测环的方法（无向图检测环（DFS思路分析）-CSDN博客），说明了环的定义：环是指一条路径的起点和终点是同一个顶点，并且路径中的边各不相同。根据这个定义，无向图中的环和有向图中的环还是有区别的，因为无向图中的边是没有方向的，但是有向图的边有方向，举例来说，在无向图中：
上图不存在环，因为路径中的边相同。但是在有向图中：
这就是一个环，因为路径中的边各不相同。有向图中的环是指沿着边的方向形成一个闭合回路，其中路径的顶点可以重复，但边不能重复。
无向图中判断是否存在环可以简单地通过检查邻居节点是否访问过，并且不是父节点来判断环的存在。但在有向图中，由于边是有方向性的，这意味着路径必须遵循这些方向。如果我们只依赖于顶点是否访问过，可能会错误地认为存在环。比如下面这张图：
对于上图，当我们使用DFS遍历的时候，从A-C遍历以后，C会被标记为已访问，但是当我们遍历到B的时候，发现C已经访问过了，但是C并非是B的父节点A，由此来判断图中存在环是错误的，根本的原因就是有向图的环要按照边的方向回到起点才可以。
二 思路分析
根据下面这张图，思考一下，有向图如何检测环呢？
我们可以发现，有向图中的环必须是沿着一个方向的，比如A->B->D->A，也就是说，环中的顶点都在同一个路径中。那么，如何判断顶点都在同一个路径中呢？
我们知道DFS使用的是递归，在执行递归函数时，系统使用递归栈存储每次函数调用的相关信息，一旦发现某个路径走完了（比如A->C），那么就将当前的调用弹出递归栈，然后将下一个路径压栈(比如A->B->D->A)。
根据上面的分析，接下来我们来梳理递归过程，并使用三色法标记每个顶点的颜色
将DFS中节点的状态分为三种
未访问（白色，未遍历到的顶点）
正在访问 （灰色，当前路径中的顶点）
已访问 （黑色，不在当前路径中的顶点）
(1) 初始化所有顶点为白色
(2) 从A开始，调用dfs(A)，将调用A方法的信息压栈，A标记为灰色
(3) dfs(A)：遍历A的邻居，在第一次遍历时找到了邻居C，调用dfs(C)，将调用C方法的信息压栈，将C标记为灰色
(4) dfs(C)：遍历C的邻居，发现没有邻居，方法执行完毕，将C方法的信息弹栈，dfs(C)函数调用结束了，此时C的处理完成了，C被标记为黑色，并且控制流返回到了调用dfs(C)的地方。
(5) 控制流回到dfs(A)方法的调用，继续下一轮循环,第二轮遍历找到了邻居B，调用dfs(B), 将B标记为灰色
(6) dfs(B)：遍历B的邻居，在遍历时找到了邻居D，调用dfs(D)， 将D标记为灰色
(7) dfs(D)：遍历D的邻居，在遍历时找到了邻居A，发现A是灰色的，说明存在环。理由：这时候dfs(A)还没有出栈，依然在递归栈中，由于dfs(A)是按照边的方向遍历的，所有从A出发但不包含在A->B->D这条路径中的分支已经被完全遍历并标记为黑色（比如C）。也就意味着在当前路径中已经存在A，现在又遇到了A，那么说明存在一个环。结果如图所示
三 步骤
步骤 1: 初始化
创建两个哈希表 visited 和 onStack，用于追踪节点的访问状态。
visited：用来记录节点是否已经被访问过，初始时所有节点都设置为 false。
onStack：用来记录当前递归调用栈中包含的节点，初始时所有节点也设置为 false。
步骤 2: 遍历每个节点
对于图中的每一个节点，如果它还没有被访问过（即 visited[node] == false），则以该节点作为起点启动一次DFS遍历。
步骤 3: 深度优先搜索 (DFS)
对于每一次DFS遍历，执行以下操作：
将当前节点标记为正在访问（灰色），即设置 visited[node] = true 和 onStack[node] = true。
遍历当前节点的所有邻居节点：
如果一个邻居节点没有被访问过，则对该邻居节点进行递归的DFS调用。
如果在DFS过程中遇到一个已经在递归栈中的邻居节点（即 onStack[neighbor] == true），那么说明存在一条从这个邻居回溯到当前节点的路径，因此存在环。
当DFS结束对当前节点的处理后，将该节点从递归栈中移除，即设置 onStack[node] = false，并将该节点标记为已访问（黑色），尽管在这个算法中我们不会显式地将节点标记为黑色，因为一旦一个节点不再位于递归栈中，就相当于它已经被完全处理过了。
步骤 4: 结束条件
如果在整个遍历过程中发现了环，则立即返回 true 表示图中存在环。
如果遍历了所有节点都没有发现环，则返回 false 表示图中不存在环。
算法终止
当所有的节点都被访问过且没有找到环，或者当找到了环并立即返回时，算法终止。
四 代码
这里使用jgrapht包中提供的有向图SimpleDirectedWeightedGraph
import org.jgrapht.Graphs;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleDirectedWeightedGraph;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class JudgeDirectedLoop {
private static final Set<String> visited = new HashSet<>();
private static final Set<String> onStack = new HashSet<>();
private static boolean hasCycle = false;
public static void main(String[] args) {
SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> graph = new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class);
// 添加顶点
String v1 = "v1";
String v2 = "v2";
String v3 = "v3";
graph.addVertex(v1);
graph.addVertex(v2);
graph.addVertex(v3);
// 添加边
DefaultWeightedEdge edge12 = graph.addEdge(v1, v2);
graph.setEdgeWeight(edge12, 1.0);
DefaultWeightedEdge edge23 = graph.addEdge(v2, v3);
graph.setEdgeWeight(edge23, 1.0);
DefaultWeightedEdge edge31 = graph.addEdge(v3, v1);
graph.setEdgeWeight(edge31, 1.0);
// 遍历所有顶点，确保每个连通分量都被检查
for (String vertex : graph.vertexSet()) {
if (!visited.contains(vertex)) {
dfs(graph, vertex);
}
}
System.out.println("是否存在环：" + JudgeDirectedLoop.hasCycle);
}
public static void dfs(SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> graph, String current) {
if (hasCycle) {
return;
}
visited.add(current);
// 将节点标记为正在访问（灰色）
onStack.add(current);
// 获取指定顶点的所有邻居顶点
List<String> neighborVertexList = Graphs.successorListOf(graph, current);
for (String neighborVertex : neighborVertexList) {
// 未访问，则递归访问
if (!visited.contains(neighborVertex)) {
dfs(graph, neighborVertex);
// 如果邻居已经在递归栈中（灰色），则存在环
} else if (onStack.contains(neighborVertex)) {
hasCycle = true;
return;
}
}
// 标记节点为已访问（黑色），并从递归栈中移除
onStack.remove(current);
}
}
另外，jgrapht还提供检测环的方法CycleDetector，但是只针对有向图
CycleDetector<String, DefaultWeightedEdge> detector = new CycleDetector<>(graph);
boolean hasCycle = detector.detectCycles();
System.out.println("是否存在环：" + hasCycle);
五 思考
还有没有其它的检测环的方法，哪种方式更好呢？