I was reading about Graphs. Almost all texts, are solving problems with acyclic graphs only. So I just wanted to try cyclic graph.
Carlos, As you said, its really difficult to come up with a generic solution it seems... But still me and my friend Shyam is working on this. We are just discussing all the possibilities like 'using a counter in the node and incrementing it till it reaches the degree of that node, book keeping of visited nodes from current node...' We are still working on this... *:)* On Mon, Nov 22, 2010 at 10:57 PM, Carlos Guia <[email protected]> wrote: > 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]<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]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
