algorithm – How to find maximum spanning tree?

algorithm – How to find maximum spanning tree?

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.

From Maximum Spanning Tree at Wolfram MathWorld:

A maximum spanning tree is a spanning tree of a weighted graph having maximum weight. It can be computed by negating the weights for each edge and applying Kruskals algorithm (Pemmaraju and Skiena, 2003, p. 336).

algorithm – How to find maximum spanning tree?

If you invert the weight on every edge and minimize, do you get the maximum spanning tree? If that works you can use the same algorithm. Zero weights will be a problem, of course.

Leave a Reply

Your email address will not be published.