Simple graph with one cycle brain teaser

RedSon

Given a directed graph of k-nodes such that the last node creates a cycle with any other node determine which node the last node's edge points to using the minimum amount of resources and without having the ability to change the data in the node.

Expand|Select|Wrap|Line Numbers

 
Visual:

O ---> O ---> O ---> ... ---> O --+

              ^                   |

              |                   |

              +-------------------+

This is seriously not a homework question. You can't mark the node as "visited" and you are discouraged from using any other data structures like copies of the linked list or additional boolean arrays and what not. The best solution will use a minimum amount of memory. Solutions that are bounded by large big Ohs will be fine too.

I've been thinking about this all day. Its quite a brain teaser. How do you figure it out by using only a few pointers and maybe one or two temporary node variables?

JosAH

Expand|Select|Wrap|Line Numbers

 Node findCycle(Node current, int k, Node target) {

   if (current == target) return current; // found a cycle?

   if (k == 0) return null; // not allowed to probe any further?
 
   for (all outgoing edges from current) // probe k steps from this node

      if (findCycle(next, k-1, current) != null)

         return current;

   // no cycle found; try further nodes:

   for (all outgoing edges from current) 

      if (findCycle(next, k, next) != null) // next node target of a cycle?

         return next;

   return null;

}

The big-Oh is terrible: from every node k steps are done at most to find a cycle
where k is the number of nodes in the graph.

kind regards,

Jos

Motoma

Traverse the graph backwards.

Simple graph with one cycle brain teaser

re: Simple graph with one cycle brain teaser

re: Simple graph with one cycle brain teaser

Similar Software Development bytes

/bytes/development

/bytes/it

/bytes/about