Since there is no mention of weights, you are looking for any spanning tree. Primm and Kruskal are for _minimum_ spanning tree. They are overkill for this problem.
You can construct a spanning tree in any graph with DFS. Just record every edge you find that reaches a vertex that has never been visited before. This has to find every vertex, and since you are recording only the first edge used to arrive at each vertex, these edges must form a tree. This works even if there are cycles. The algorithm is O(| E|). Note that in general a graph doesn't have a single root. So you'd search from all roots. Another way to think about this: introduce your own dummy root and edges to each vertex where there are no incident "in" edges. Of course you don't report the dummy edges. On Mar 12, 1:09 pm, atul anand <atul.87fri...@gmail.com> wrote: > i guess they were talking abt spanning tree , so you can use prism or > kruskal algo to do the same. > > > > > > > > On Mon, Mar 12, 2012 at 3:05 PM, Umer Farooq <the.um...@gmail.com> wrote: > > Hello friends, > > > I recently had an onsite MS interview. One of the questions that they > > asked was: > > > - Given a directed graph, write a program that takes root of the graph > > and returns root of a tree which comprises of all the nodes of the graph > > in > > the same way as they appeared in the graph (the graph contains no > > cycles). > > > -- > > Umer > > > -- > > 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?hl=en. -- 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?hl=en.
