Questions tagged [cycle-detection]
42 questions
36
votes
16 answers
detecting the start of a loop in a singly linked link list?
Is there any way of finding out the start of a loop in a link list using not more than two pointers?
I do not want to visit every node and mark it seen and reporting the first node already been seen.Is there any other way to do this?
Biswajyoti Das
- 7,881
- 11
- 34
- 26
22
votes
3 answers
Can we detect cycles in directed graph using Union-Find data structure?
I know that one can detect cycles in direct graphs using DFS and BFS. I want to know whether we can detect cycles in directed graphs using Union-Find or not?
If yes, then how? and
If we can't, then why?
vinter
- 466
- 1
- 3
- 13
7
votes
1 answer
How to detect circular references in JavaScript
For example:
$ node
> var x = {}
undefined
> x.x = x
{ x: [Circular] }
Wondering the sort of structures are they using to accomplish this, because it's not encoded directly into what I just did. It seems like they would do something like:
var graph…
Lance
- 75,200
- 93
- 289
- 503
7
votes
1 answer
Generate a directed graph with n cycles
I want to generate a directed graph that contains exactly the specified amount of cycles with their respective length. For example, the graph should contain:
2 cycles of the size 3
1 cycle of the size 5
Does such an algorithm already exist? If…
derbenoo
- 303
- 1
- 2
- 10
6
votes
1 answer
Most efficient way of finding circular references in list
Given the following list of redirects
[
{
"old": "a",
"target": "b"
},
{
"old": "b",
"target": "c"
},
{
"old": "c",
"target": "d"
},
{
"old": "d",
"target":…
JOSEFtw
- 9,781
- 9
- 49
- 67
6
votes
1 answer
Finding cycles in a (not quite) Latin square
Given a matrix of size m X n with no repetition of values in rows or columns, is there an efficient method of detecting cycles?
For example, here is a sample matrix:
3 5 2 9 7 4
4 3 6 1 8 7
1 4 7 5 2 9
9 8 3 2 6 1
…
Jim White
- 211
- 1
- 6
4
votes
1 answer
Time complexity for detecting a cycle in a graph
I am trying to understand the time complexity of some efficient methods of detecting cycles in a graph.
Two approaches for doing this are explained here. I would assume that time complexity is provided in terms of worst-case.
The first is…
bollock1
- 85
- 1
- 7
3
votes
3 answers
Cycle Detection Algorithm: Is there a condition for Tortoise and Hare to enter into cycle?
Recently I attended an interview and came accross the following question which I am not able to figure out.
Question-1:
As per the proof which I read Tortoise moves 1 step and Hare moves 2 steps at a time. I understood this and they will meet at…
Amarnath
- 8,736
- 10
- 54
- 81
3
votes
1 answer
Tarjan's cycle detection: missing cycles
I have tried out Tarjan's algorithm for cycle detection with the implementation from http://learn.yancyparedes.net/2012/03/strongly-connected-components-using-tarjans-algorithm/ .
The following graph was used for testing:
a b
a c
b a…
MarryS
- 165
- 2
- 10
2
votes
1 answer
Getting wrong answer for simple algorithm with cycle detection
I am solving this problem, a part of the problem that is giving me troubles is formulated as follows:
a. Start from index i=0;
b. Jump to index i=A[i];
c. If the current index i is outside the valid bound of [0..N-1],
print “Out” and stop;
d. Else…
Bart Louwers
- 873
- 9
- 28
2
votes
2 answers
Cycle detection in java
I'm working on a hackerrank problem and it seems like no matter the variation of the solution I try, I can't get the cycle detection to work.
Here's the code I'm using
static boolean hasCycle(SinglyLinkedListNode head) {
if (head == null)…
ceckenrode
- 4,543
- 7
- 28
- 48
2
votes
0 answers
Efficient gremlin query to find a cycle in a graph
I have a big TinkerGraph (~80.000 vertices, ~160.000 edges) and I need to detect if there is a cycle in it using the Apache TinkerPop/Gremlin query language. If any, I would like to obtain the vertices of one of the cycles.
Is there a way to write a…
Federico
- 1,925
- 14
- 19
2
votes
2 answers
BFS cycle detection
Could someone provide a step by step pseudocode using BFS to search a cycle in a directed/undirected graph?
Can it get O(|V|+|E|) complexity?
I have seen only DFS implementation so far.
Turbo
- 77
- 1
- 10
2
votes
3 answers
What is a rho shaped sequence?
I came across this in the solution presented by Saurabh Kr Vats at this http://www.careercup.com/question?id=14990323
He says:
# Finally, the sequence could be "rho-shaped." In this
# case, the sequence looks something like this:
#
# x_0 -> x_1…
tanvi
- 927
- 5
- 17
- 32
2
votes
1 answer
Cycle detection in non-iterated sequence
My understanding is that tortoise-hare like algorithms works on iterated sequences
That is, for any x, succ(x) = x0.
I would like to implement an algortihm that can detect cycles in both deterministic and non-deterministic infinite repeating…
lsund
- 744
- 5
- 16