prims and krushkal dont' work for directed graphs On Tue, Jun 22, 2010 at 6:44 AM, Gene <gene.ress...@gmail.com> wrote:
> On Jun 20, 7:48 am, jalaj jaiswal <jalaj.jaiswa...@gmail.com> wrote: > > give an algo to find a minimum spanning tree of a directed graph ?? > > > > -- > > With Regards, > > Jalaj Jaiswal > > +919026283397 > > B.TECH IT > > IIIT ALLAHABAD > > Kruskal's algorithm: > > Remove all the edges in the graph. Re-insert them in ascending order > of weight, except that when adding an edge would cause a cycle, throw > it away. Stop when you have connected all the vertices. > > Primm's algorithm: > > Pick a vertex. Remove it from the graph. This is the first vertex in > the MST. Now pick the smallest edge that connects a removed vertex to > one still in the original graph. Move that edge and its vertex to the > MST. Stop when all the vertices are in the MST. > > The interesting part of both algorithms is picking good algorithms to > keep track of cycles and edge weights. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.
