1

Here is a tree:

  1. There will be one root.

  2. Each tree node has zero or more children.

  3. It is allowed that two nodes points to the same child. Say, both node A and node B has child C.

However, it is prohibited that,

Node A is an offspring of Node B, and Node B is an offspring of Node A.

One prohibited case is

Node A has a child Node C and Node D,

Both Node C and D has a child node E,

Node E has a child of A.

The question is, how to determine this circle in a fastest manner?

UPDATE: I realize this is to find any cycle in a directed graph. Just now I managed to think out a solution similar to Tarjan's algorithm.

Thanks for comments.

Community
  • 1
  • 1
SiLent SoNG
  • 4,270
  • 4
  • 27
  • 31
  • 4
    This is called a "cycle" (not circle) in graph theory. You are trying to verify that a give graph is a "directed acyclic graph" or DAG for short. http://en.wikipedia.org/wiki/Directed_acyclic_graph – Wim Coenen Feb 17 '10 at 13:53
  • Also, this question has already been asked and answered here: http://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph – Wim Coenen Feb 17 '10 at 13:56
  • 1
    The data structure you have is a directed graph, not a tree. A tree node can't have multiple parents. – interjay Feb 17 '10 at 14:10

2 Answers2

6

Do a Depth First Search through the tree. If at any point you find a node that is already in your backtracking stack, there is a circle.

David Schmitt
  • 58,259
  • 26
  • 121
  • 165
0

circles can be found using 2 pointers and advancing them at different intervals. Eventually the pointers will match, indicating a loop, or the "faster" one will reach then end. The question is usually asked of linked lists though, not trees.

No Refunds No Returns
  • 8,092
  • 4
  • 32
  • 43
  • I'm not sure this would be the *fastest manner* of doing it, but rather the *lowest memory overhead manner*. Also, it sounds complicated to do for a tree. – Hans W Feb 17 '10 at 13:59
  • The problem will be easy for a linked list. But consider this problem - the tree wil have multiple ends. Instead a linked list has only one end. – SiLent SoNG Feb 17 '10 at 15:09
  • yeah ... that's why I said the question is usually asked of lists, not trees. you'd have to run this for each node of the tree using a queue to remember the "next" nodes of each node as new starting points. It would be ugly. – No Refunds No Returns Feb 17 '10 at 16:23