Что не так с моим методом hasCycle (), использующим DFS?

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

Ваш код не работает, потому что:

---

Функция hasCycle (Graph g) неверна, потому что:

• возвращает true / false на основе всех узлов, доступных с первого узла(что если граф отключен?)

---

Функция hasCycle (График g, вершина пред, вершина u, множество известных) также неверна:

• Вы возвращаетеЗначение true, только если вы находите соседний с текущим узлом узел, который не посещен и не совпадает с предыдущим узлом, который не имеет смысла для поиска цикла.

---

Предложение:

Обратитесь к некоторым учебникам, таким как: https://www.geeksforgeeks.org/detect-cycle-in-a-graph/ и попробуйте понять, как работает алгоритм поиска циклов, затем попробуйте реализовать его

Answer 2

Этот код будет работать.Я не проверял.

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, говорят, что граф имеет цикл.

Answer 3

Может быть, переместить оператор else на внешнее выражение if ... Кроме того, функция, принимающая только график, не должна возвращаться на первой итерации ...