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