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.

Although this thread is too old, I have another approach for finding the maximum spanning tree (MST) in a graph G=(V,E)

We can apply some sort Prim's algorithm for finding the MST. For that I have to define Cut Property for the maximum weighted edge.

Cut property: Let say at any point we have a set S which contains the vertices that are in MST( for now assume it is calculated somehow ). Now consider the set S/V ( vertices not in MST ):

Claim: The edge from S to S/V which has the maximum weight will always be in every MST.

Proof: Let's say that at a point when we are adding the vertices to our set S the maximum weighted edge from S to S/V is e=(u,v) where u is in S and v is in S/V. Now consider an MST which does not contain e. Add the edge e to the MST. It will create a cycle in the original MST. Traverse the cycle and find the vertices u' in S and v' in S/V such that u' is the last vertex in S after which we enter S/V and v' is the first vertex in S/V on the path in cycle from u to v.

Remove the edge e'=(u',v') and the resultant graph is still connected but the weight of e is greater than e' [ as e is the maximum weighted edge from S to S/V at this point] so this results in an MST which has sum of weights greater than original MST. So this is a contradiction. This means that edge e must be in every MST.

Algorithm to find MST:

Start from S={s}   //s is the start vertex
while S does not contain all vertices
 do 
 {
  for each vertex s in S
  add a vertex v from S/V such that weight of edge e=(s,v) is maximum 
  }
end while

Implementation: we can implement using Max Heap/Priority Queue where the key is the maximum weight of the edge from a vertex in S to a vertex in S/V and value is the vertex itself. Adding a vertex in S is equal to Extract_Max from the Heap and at every Extract_Max change the key of the vertices adjacent to the vertex just added.

So it takes m Change_Key operations and n Extract_Max operations.

Extract_Min and Change_Key both can be implemented in O(log n). n is the number of vertices.

So This takes O(m log n) time. m is the number of edges in the graph.

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 Kruskal's algorithm (Pemmaraju and Skiena, 2003, p. 336)."