v easy...dfs style se agey badhtey jao.. her node ko mark kerte jao.. when u come across an already marked node..hurray!u have a cycle!
the tougher part is to find ALL the cycles of a graph... ye karo to maney... nihit and i had spent quite sm tm on this one...every graph has a CYCLE BASE(a set of cycles whose nodes' combinations span all the cycles of the graph)using this funda i had arrived to a conclusion tht this preoblem is np complete.. now if u want i can recall my approach n let u guys know.. dnt r'ber tht exactly now
ghoida not that easy.... after u reach a leaf node(using DFS) u will backtrack to its parent....the parent is marked.. so u will say that thr is a loop even when thr isn't any! a small modification in the DFS wud however solve the problem!
Posts
3 comments:
v easy...dfs style se agey badhtey jao.. her node ko mark kerte jao.. when u come across an already marked node..hurray!u have a cycle!
the tougher part is to find ALL the cycles of a graph... ye karo to maney... nihit and i had spent quite sm tm on this one...every graph has a CYCLE BASE(a set of cycles whose nodes' combinations span all the cycles of the graph)using this funda i had arrived to a conclusion tht this preoblem is np complete.. now if u want i can recall my approach n let u guys know.. dnt r'ber tht exactly now
ghoida not that easy....
after u reach a leaf node(using DFS) u will backtrack to its parent....the parent is marked.. so u will say that thr is a loop even when thr isn't any!
a small modification in the DFS wud however solve the problem!
i'l think on the problem u hve mentioned.
finding all the cycles is tough .. please do it algo god sanjib :)
Post a Comment