On Jun 20, 7:48 am, jalaj jaiswal <[email protected]> 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
