使用DFS的hasCycle（）方法出了什么问题？

Question

我试图制作一个简单的hasCycle()方法来检测图中的循环，但我遇到了一些问题。

我使用的代码是：

public static boolean hasCycle(Graph g, Vertex prev, Vertex u, Set<Vertex> known) {
known.add(u);

for(Vertex temp : g.getNeighbours(u)){
  if(!known.contains(temp)){
    if(hasCycle(g,u,temp,known))
      return true;

    else if(temp != prev)  
      return true;
  }
}

return false;
}

public static boolean hasCycle(Graph g) {
Set<Vertex> known = new TreeSet<>();

for(Vertex u : g.getAllVertices()){
  known.add(u);
  return hasCycle(g,u,u,known); // is this correct, how do I overload this method
}

return false;
}

当我测试它为这样的输入：

public static void main(String[] args){
    Graph g = new Graph();
    Vertex v = new Vertex(0);
    Vertex w = new Vertex(1);

    g.addVertex(v);
    g.addVertex(w);
    g.addEdge(v, w);
    System.out.println(hasCycle(g)); // this is printing true
}

和

public static void main(String[] args){
    Graph g = new Graph();
    Vertex v = new Vertex(0);

    g.addVertex(v);
    g.addEdge(v, v);
    System.out.println(hasCycle(g)); // this is printing false
}

我无法理解出了什么问题。我将不胜感激任何帮助。

Answer 1

也许将else语句移动到外部if ...而且仅使用图形的函数不应该在第一次迭代时返回...

Answer 2

您的代码失败原因：

---

函数hasCycle（图g）是错误的，因为：

• 它基于从第一个节点可到达的所有节点返回true / false（如果图形断开连接怎么办？）

---

函数hasCycle（Graph g，Vertex prev，Vertex u，Set known）也是错误的：

• 仅当您找到未访问的当前节点的相邻节点并且不等于找不到查找周期的前一节点时，才返回true。

---

建议：

请参考以下教程：https://www.geeksforgeeks.org/detect-cycle-in-a-graph/并尝试了解循环查找算法的工作原理，然后尝试实现它

Answer 3

这段代码可行。我没有测试过。

import java.util.*;

public class DetectCycle {
  public boolean dfs(Graph g, Vertex u, Set<Vertex> known) {
    known.add(u);
    for (Vertex v: g.getNeighbours(u)) {
      if (known.contains(v)) {
        return true;
      }
      return this.dfs(g, v, known);
    }
    return false;
  }

  public boolean hasCycle(Graph g) {
    Set<Vertex> known = new Set<Vertex>();
    for (Vertex v: g.getAllVertices()) {
      if (known.contains(v)) {
        continue;
      }
      known.add(v);
      if (this.dfs(g, v, new Set<Vertex>())) {
        return true;
      }
    }
    return false;
  }

  public static void main(String[] args){
    Graph g = new Graph();
    Vertex v = new Vertex(0);
    Vertex w = new Vertex(1);

    g.addVertex(v);
    g.addVertex(w);
    g.addEdge(v, w);
    System.out.println(this.hasCycle(g));
  }
}

请注意，我正在为每个DFS调用传递一个新初始化的已知集。每个DFS都有自己的访问顶点副本。如果我们在单个DFS调用中遇到两次顶点，则表示该图形具有一个循环。