如何使用itarative方法检测循环

Question

我正在努力学习如何检测循环。我看到很多使用递归的例子，但我想以迭代的方式实现。这是我的密码

public boolean cycleDetection(int[][] edges, int source ) {
     Map<Integer, List<Integer>> graph = new HashMap();
        for (int[] edge : edges) {
            graph.putIfAbsent(edge[0], new ArrayList());
            graph.get(edge[0]).add(edge[1]);
        }
        Stack<Integer> stack = new Stack();
        Set<Integer> visited = new HashSet();
        
        stack.push(source);
        visited.add(source);
        while(!stack.isEmpty()) {
            int curr = stack.pop();
            visited.add(curr);
            if(graph.containsKey(curr)) {
                for(int i :  graph.get(curr)) {
                    
                    if(visited.contains(i)) {
                        return true;
                    }
                    stack.push(i);
                }
            }
            
        }
    return false;
}

它没有按预期工作

    int[][] vertex = { {0 , 1 }, {0,3}, {1,2},{2,1} }; // Has Cycle
    int[][] vertex = { {0 , 1 }, {0,2}, {1,3},{2,3} }; // No Cycle

我在这里遗漏了什么逻辑？

Answer 1

问题是你也在检测交叉边。

在您的示例中，发现顺序（在示例2中）是：

0 -> 1 -> 3 -> 2 -> 3

现在，当你第二次看到3时——你注意到它已经被访问过了——然后说有一个循环。然而，这是一个交叉边——你发现了它，但通过一个不同的分支，事实上这不是一个循环。

一种解决方案（对代码进行最少的修改）-虽然可能不是最佳方案，但一旦您完成了探索，就从访问的中删除一个节点。

为什么它会起作用？

• 如果有一个循环——你会发现它，因为在你重新发现它之前，节点并没有从访问的数据库中删除。一旦你发现了算法，它就会结束
• 如果没有循环，您将耗尽一条路径，并将其所有节点从访问的路径中移除。由于没有循环，算法将“耗尽”选项并最终终止

在DFS的迭代代码版本中实现可能有点棘手（因为您希望“一旦从递归中恢复”就模仿这样做），但应该是可能的。祝你好运！