How to find maximum spanning tree?

Question

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 1

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.

Answer 2

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.

Answer 3

From this website:

"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)."

Answer 4

Let me provide an improvement algorithm:

• first construct an arbitrary tree (using BFS or DFS)
• then pick an edge outside the tree, add to the tree, it will form a cycle, drop the smallest weight edge in the cycle.
• continue doing this util all the rest edges are considered

Thus, we'll get the maximum spanning tree.

---

This tree satisfies any edge outside the tree, if added will form a cycle and the edge outside <= any edge weights in the cycle

In fact, this is a necessary and sufficient condition for a spanning tree to be maximum spanning tree.

Pf.

Necessary: It's obvious that this is necessary, or we could swap edge to make a tree with a larger sum of edge weights.

Sufficient: Suppose tree T1 satisfies this condition, and T2 is the maximum spanning tree.

Then for the edges T1 ∪ T2, there're T1-only edges, T2-only edges, T1 ∩ T2 edges, if we add a T1-only edge(x1, xk) to T2, we know it will form a cycle, and we claim, in this cycle there must exist one T2-only edge that has the same edge weights as (x1, xk). Then we can exchange these edges will produce a tree with one more edge in common with T2 and has the same sum of edge weights, repeating doing this we'll get T2. so T1 is also a maximum spanning tree.

Prove the claim:

suppose it's not true, in the cycle we must have a T2-only edge since T1 is a tree. If none of the T2-only edges has a value equal to that of (x1, xk), then each of T2-only edges makes a loop with tree T1, then T1 has a loop leads to a contradiction.

---

This algorithm taken from UTD professor R. Chandrasekaran's notes. You can refer here: Single Commodity Multi-terminal Flows

Answer 5

yes it does,

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

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.

Answer 6

Only reversing the sorting order, and choosing a heavy edge in a vertex cut does not guarantee a Maximum Spanning Forest (Kruskal's algorithm generates forest, not tree). In case all edges have negative weights, the Max Spanning Forest obtained from reverse of kruskal, would still be a negative weight path. However the ideal answer is a forest of disconnected vertices. i.e. a forest of |V| singleton trees, or |V| components having total weight of 0 (not the least negative).