If you just want to traverse the graph DFS works well. And if you want to find a minimum spanning tree, kruskal's algorthim works.
On Tue, Nov 23, 2010 at 10:13 AM, Eagle <[email protected]> wrote: > You will have to add logic to your program to detect CCCs > (circular > sub-paths), bridge nodes (if any) and the number of CCCs a bridge node > connects. After this, keep on subtracting the visits to bridge node > from the > number of CCCs it connects; when this becomes zero, it means that now > the > node can not be re-visited. > > On Nov 23, 12:27 am, Sakthi Priyan <[email protected]> > wrote: >> 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. > > -- 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.
