How to find maximum spanning tree?

algorithm minimum-spanning-tree greedy kruskals-algorithm
user467871 picture user467871 · Feb 14, 2011 · Viewed 99.4k times · Source

Does the opposite of Kruskal's algorithm for minimum spanning tree work for it? I mean, choosing the max weight (edge) every step?

Any other idea to find maximum spanning tree?

Answer

systemkern picture systemkern · Feb 14, 2011

Yes, it does.

One method for computing the maximum weight spanning tree of a network G – due to Kruskal – can be summarized as follows.

  1. Sort the edges of G into decreasing order by weight. Let T be the set of edges comprising the maximum weight spanning tree. Set T = ∅.
  2. Add the first edge to T.
  3. Add the next edge to T if and only if it does not form a cycle in T. If there are no remaining edges exit and report G to be disconnected.
  4. If T has n−1 edges (where n is the number of vertices in G) stop and output T . Otherwise go to step 3.

Source: https://web.archive.org/web/20141114045919/http://www.stats.ox.ac.uk/~konis/Rcourse/exercise1.pdf.

Related questions

When should I use Kruskal as opposed to Prim (and vice versa)?

I was wondering when one should use Prim's algorithm and when Kruskal's to find the minimum spanning tree? They both have easy logics, same worst cases, and only difference is implementation which might involve a bit different data structures. So …

Read More
Difference between Prim's and Dijkstra's algorithms?

What is the exact difference between Dijkstra's and Prim's algorithms? I know Prim's will give a MST but the tree generated by Dijkstra will also be a MST. Then what is the exact difference?

Read More
Use Dijkstra's to find a Minimum Spanning Tree?

Dijkstra's is typically used to find the shortest distance between two nodes in a graph. Can it be used to find a minimum spanning tree? If so, how? Edit: This isn't homework, but I am trying to understand a question …

Read More