Re: How to detect circle in a directed graph?


"George2 via JavaKB.com" <u14844@uwe> wrote in message
news:59e4d1068cc90@xxxxxx
> Larry,
>
>
> Larry Barowski wrote:
>>>>>>My application needs a feature to detect whether a directed graph
>>>>>>contains
>>[quoted text clipped - 9 lines]
>>>
>>> Is it difficult to adapt for directed graphs.
>>
>>Impossible, if the goal is O(1) space complexity. I guess
>>you could use a graph walk that reverses only at fully
>>explored nodes, which might make a fun animation but
>>would be less time and space efficient than a DFS cycle
>>test.
>
> I can not believe that cycle detection algorithm can work with only O(1).
> Could you privide sample implementation or reference resource please?

That is my point. Hare & Tortoise uses O(1) space for cycle
detection in a linked list. This is its main benefit over the
obvious algorithm, which uses O(n) space. The speed
may be slightly slower or faster than the obvious algorithm
by a constant factor. For the Hare & Tortoise style cycle
detection algorithm for directed graphs that I propose above,
the space and time complexity is the same as for DFS, and I
would expect space and time use to be worse by constant
factors, so there would be no practical benefit. It should
work though. For a depth first graph walk that reverses
only at fully explored nodes, any repeated edge is part of
a cycle, and if a cycle exists, the walk will become
trapped in it. If the follower catches the leader at the same
edge (not just the same node), a cycle has been found.


.

Relevant Pages
Loading