> > reach the other. So, if I mark node 1 as visited at first, the program will > start from 1 and lets say it touches 2 and then it ll touch 3. From 3, it > has to go to 1 and by that time node 1 is marked as visited. So program 'll > halt there and 'll give wrong result.
This part, for that example, can easily be solved as this for each node n, mark all nodes as not visited start walk from n end for However, I don't hit that solves the problem you want, I'm pretty sure there are other graphs that actually need to visit a node more than once. I haven't put much thought to it, but the problem the strikes me as NP-hard. If I'm correct, then you shouldn't be able to solve it efficiently for the general case. For a small number of nodes you could backtrack or use dynamic programming. Where does this problem come? Is it a contest problem, you created it out of curiosity, school assignment, etc? Carlos Guía On Mon, Nov 22, 2010 at 4:37 AM, Sakthi Priyan <[email protected] > wrote: > I am sorry. I didn't explain my problem clearly at first shot. > > It goes like this > > Assume there are five nodes in a graph. I am giving the Adjacency Matrix > here. > > 1 2 3 4 5 > 1 0 1 1 1 1 > 2 1 0 1 0 0 > 3 1 1 0 0 0 > 4 1 0 0 0 1 > 5 1 0 0 1 0 > > Now I need to visit all the nodes with minimum weights crossed. This is the > problem :( > > Here we have two closely connected components (CCC), 123 and 145. And node > 1 acts like a bridge between those CCC. If I enter any of those CCC, I need > to touch node 1 again to reach the other. So, if I mark node 1 as visited at > first, the program will start from 1 and lets say it touches 2 and then it > ll touch 3. From 3, it has to go to 1 and by that time node 1 is marked as > visited. So program 'll halt there and 'll give wrong result. > > Please suggest... > > > On Mon, Nov 22, 2010 at 9:52 AM, vineel yalamarth < > [email protected]> wrote: > >> >> >> Try using a visited flag for all the nodes. Initialise it to zero and >> toggle it when you traverse through it,.Based on status of visited flag, you >> can avoid visiting the visited nodes. >> >> Regards, >> Vineel. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "google-codejam" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<google-code%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/google-code?hl=en. >> > > > > -- > - Thanks and Regards, > > *Sakthipriyan* > > -- > You received this message because you are subscribed to the Google Groups > "google-codejam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<google-code%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. > -- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
