@Dave : DFS doesnt work that way. you might like to brush up tree traversal :D
_dufus On Sep 13, 10:27 pm, Dave <dave_and_da...@juno.com> wrote: > Suppose the graph consists of three nodes in a triangle. You number > your starting node at level 1 and the other two at level 2. How do you > proceed? > > Dave > > On Sep 12, 9:27 pm, Gene <gene.ress...@gmail.com> wrote: > > > On Sep 6, 5:28 am, ankur aggarwal <ankur.mast....@gmail.com> wrote: > > > > google question : find triangle in a graph Given an undirected graph, > > > design a O(V+E) algo to detect whether there is a triangle in the graph ot > > > not. > > > Just do a depth first search, numbering each node with it's depth as > > you find it. If you are searching from a node at depth D and discover > > a back-edge to depth D - 2, you have found a triangle. It's pretty > > easy to show that if no such back-edges are found, there are no > > triangles. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
