9

could some please help me understand how to find cycles in graphs in laymans terms?

I have read other questions, such as This one and also some of the wikipedia pages, but they seem to descend rather quickly into mathematical jargon.

I have a model of the graph in java, modelling nodes, and 'in' and 'out' edges - and the model knows nodes only connected in one direction, this allows me to find the leaf nodes as a starting point, my plan was to walk back up the graph from each of these leaf nodes, for each "walk", keeping a list of all the other nodes I've found on my route. If I see something already in the list at any point, I'll know I've found a cycle in the graph. This however feels a little simplistic.

I'm sure this is a solved problem, it would just be nice if it could be explained in simple terms.

-ace

2 Answers 2

6

The simplest way I can think of to explain spotting graph cycles in layman's terms, is something like this:

  • First, I assume you know the basics of what a graph is, and what nodes and edges are. This example assumes that you have a graph in which all edges are one-way only.
  • Create your graph, and select one node as the starting point.
  • Create a container object of some sort (a list or hash would work best). Call it "Visited".
  • Create a second container object (a queue would be ideal here) and call it "Open".
  • Add the starting node to the Open list.
  • Repeat while the Open list is not empty:
    • Remove the first item from Open and call it Current
    • If Current exists in Visited, you have a cycle.
    • If not, add Current to Visited, and then add all nodes that Current can reach from its outbound edges to Open.
  • If Open ends up empty and no cycles have been detected, then you don't have any cycles. (At least not in the reachable set originating from the starting point, which is not necessarily the entirety of your graph if you have islands in your graph.)
0
0

Basically, you do a breadth first search on the graph and keep track of which nodes you have visited using a hashmap.

At any point of time, if you encounter a node that has already been visited(present in hashmap), then you know that there is a cycle in the graph.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.