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?

Solution 1

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.

Solution 2

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

Solution 3

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.

Solution 4

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.

Solution 5

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

View more solutions

Comments

[Admin]

so, my assumption is true I think :)

[duffymo]

Negating the weights! I have the Skienna book, but I didn't pull that nugget out of memory. (The book is at home, so I couldn't refer.) Thanks for reminding me. I'll be good incentive to keep reading more carefully.

[Rusty Rob]

how will zero weights be a problem?

[Ankit Roy]

Zero weights will not be a problem, but if you are looking for the maximum-weight tree overall (rather than the maximum-weight spanning tree, which is constrained to visit all vertices) then negative weights will be a problem: this problem is NP-hard.

[Palec]

If the only important thing is which edges are in the minimum spanning tree, only the order of edges is relevant for Kruskal’s algorithm. And the order is the same when you negate the edge weights as when you reverse the order of the original weights.

[Chris Watts]

@banarun Very late to the party, but yes, it does.

[Stuxen]

Will it work if we sort the edges in increasing order and keep removing the edges in the same order if the graph remains connected?

[systemkern]

Yes, though it is harder to write the test (= if condition) which checks if the graph is still valid. Cheers and all the best, Rainer

[Thariq Nugrohotomo]

Interesting approach. Could you please add the complexity of your algorithm to your answer? Thanks.

[dqureshiumar]

can you elaborate, the word NEGATE

[LetsGoBrandon]

Why reversing the sorting order is not correct?