Member Avatar for nitin1

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
  • 139 Views
  • 1 Week Discussion Span
  • Latest Post Latest Post by Taywin
Member Avatar for Taywin

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

Member Avatar for nitin1

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

Member Avatar for Taywin

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
Member Avatar for nitin1

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.

Member Avatar for Taywin

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
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.