The algorithm for detecting cycles in an undirected connected graph runs a slightly modified version of DFS:

1. Pick a node current, add it to visited.
2. Set parent = current and current = current.neighbour(). Add new current to visited.
3. Repeat step 2 until the moment you get to a node that is in visited that isn't equal to parent, you have detected a cycle (ie going from node a to b to a isn't a cycle, a cycle is if you can get to a by going from a to b to c then to a).

First of all there are likely holes in my solution, so please tear it apart.

Second, if my solution is perfect, my issue is in step 3, you have to check that the node you're on hasn't been visited yet. Doesn't looking up if an element is in a list take O(n) time? And you need to do this for every node you visit? Would this not run in O(n²) then?

Extra info: I tried doing this without a "visited" list, instead just keeping track of the first node you start with r, and every time you visit a new node you check if the new node is equal to r, and this check is O(1) time. However that doesn't work in this scenario when r = A:

      C
     / \
A - B - D

Thank you

The algorithm for detecting cycles in an undirected connected graph runs a slightly modified version of DFS:

1. Pick a node current, add it to visited.
2. Set parent = current and current = current.neighbour(). Add new current to visited.
3. Repeat step 2 until the moment you get to a node that is in visited that isn't equal to parent, you have detected a cycle (ie going from node a to b to a isn't a cycle, a cycle is if you can get to a by going from a to b to c then to a).

First of all there are likely holes in my solution, so please tear it apart.

Second, if my solution is perfect, my issue is in step 3, you have to check that the node you're on hasn't been visited yet. Doesn't looking up if an element is in a list take O(n) time? And you need to do this for every node you visit? Would this not run in O(n²) then?

Extra info: I tried doing this without a "visited" list, instead just keeping track of the first node you start with r, and every time you visit a new node you check if the new node is equal to r, and this check is O(1) time. However that doesn't work in this scenario when r = A:

      C
     / \
A - B - D

Thank you

• algorithm
• undirected-graph

• 3 You don't have to use lists with linear look up. There are other data structures out there, some with O(1) look up time. – n. m. could be an AI Commented Mar 11 at 5:09

2 Answers 2

Use a set instead of an array for storing the visited nodes. Sets have O(1) lookup time, resulting in a total time complexity of O(n) for your algorithm, which is otherwise correct.

As for the statement that "going from node a to b to a isn't a cycle",

This is true if you consider simple graphs only and have to use the same edge twice, in multigraphs you may have more than one edge connecting a and b in which case a-b-a over distinct edges counts as a cycle.

Your algorithm can actually run in O(V+E). Where 'V' represents the set of vertices(or nodes) and 'E' represents the set of edges. The reason it doesn't run in O(N^2) is because we can use a HashSet data structure(which has an average look up time of O(1)) instead of a List(look up time is O(N))to keep track of the visited nodes.