How to detect a cycle in a undirected graph?

Question

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?

Answer 1

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 back edges.

And the other one is to use the union-find algorithm (aka Disjoint Set data structure) which is used in many applications for cycle detection, especially when you have an undirected graph.

Here's a few useful links about DFS and union-find algorithms for graph cycle detection to get you started:

https://www.geeksforgeeks.org/detect-cycle-undirected-graph/

https://www.geeksforgeeks.org/detect-cycle-in-a-graph/

https://www.geeksforgeeks.org/union-find/

Note: There are other ways you can detect cycles in graphs, but they are usually not as efficient as the ones mentioned above.