0

i have a undirected graph and i want to print a cycle with length >=k (given) , can you suggest me a algo ? i dont want any code, snippet. i am hoping for hint and algo for this. thanks. it is guaratned that cycle of length >=k exists.. thanks.

2
Contributors
5
Replies
7
Views
4 Years
Discussion Span
Last Post by Taywin
0

You could use Depth First Search to look for all cycles. Report back only those that have length >= k.

0

how can i print the node number included in the cycle and how will i find the length ?

0

You should keep your visited node in order. You need to keep checking whether the new node you are visiting is already in your visited list. If it is, those nodes between the duplicated nodes and its own node compose a cycle. (Remember that you keep them in order of visiting?). The number of nodes inside a cycle is the length of the cycle.

Edited by Taywin

0

that mean when i find that i have already visited this node , then i have to use a linear search that where the node is( which is included in cycle) ? right ? linear search will be costly in my case.

0

I didn't say that you could not keep another hash-liked structure as another search type for visited. In other words, if you concern about search time from a queue-liked structure of visited node, you could also have an index (hash-liked) just for checking whether the node has been visited. If so, then you could do the linear search to create a cycle.

Edited by Taywin

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.