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 -~----------~----~----~----~------~----~------~--~---
