Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 6 down vote accepted

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.)
share|improve this answer
    
Very helpful & just what I needed - thanks. –  phatmanace Feb 22 '13 at 18:26

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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