Good morning, currently I am stuck on trying to figure out how to detect a cycle in a undirected graph where the keys are strings.

my code so far:

public boolean hascycle() {
    DSHashMap<String> parent = new DSHashMap<>();
    DSHashMap<String> visted = new DSHashMap<>();
    LinkedList<String> q = new LinkedList<>();
    for (String start : graph) {
      q.add(start);
      visted.put(start, "");
      ;
      while (!q.isEmpty()) {
        String v = q.poll();
        for (String x : graph.get(v)) {
          if (!visted.containsKey(x)) {
            visted.put(x, "");
            ;
            q.add(v);
            parent.put(x, v);
          } else if (!parent.get(x).equals(v))
            return true;
        }
      }
    }
    return false;
  }

My logic so far: if the key of parent does not equal to v, it must be a new neighbor and we should return true.

When I tried checking my code with this checker:

private static void gradehascycles() {
    System.out.println("\nGrading the cycles function");
        DSGraph g = new DSGraph();
        g.addEdge("a", "b");
        g.addEdge("a", "e");
        g.addEdge("c", "b");
        g.addEdge("c", "d");
        checkExpect(g.hascycle(), false, "Square graph", 1);
}

My code returned true even though it was supposed to be false. What is the logic behind checking if a graph has a cycle or not?

CodePudding user response：

There are two classic ways of finding cycles in graphs: one is by using DFS (depth first search) algorithm and label the edges and look for Let's say that you started traversing a graph with A, you marked it as visited (I highlighted it with yellow), and then started traversing its neighbors, B, E. You marked them as visited as well and updated their parent reference to point to A, you also added them to the q. Then you extract the next element from the q, let's say it was B. According to your naming B is v, and its neighbors A and C are x's. You inspect A first. It's already been visited so you proceed to else if clause and check that parent of x (A) is v (B). But it's not, A doesn't have a parent, you compare null with v, and it's not equal, so your code returns true.