Maximum Spanning Tree

Question

Consider problem similar to a minimum spanning tree, but instead we want to find the maximum spanning tree, that is, a tree that maximums the sum of weight of the edges. Describe an efficient algorithm to find the maximum spanning tree.

Answer 1

sort the edges in the graph, greedy method choose the longest until the edges in the domain make a path from start to the end. delete the edge cannot be used and get the max spanning tree.

Answer 2

Sort all the edges in descending order based on their weights.

Start with an empty graph, which will become the Maximum Spanning Tree.

Iterate through the sorted edges. For each edge, if adding it to the current Maximum Spanning Tree doesn't create a cycle, add it to the tree. Continue this process until the Maximum Spanning Tree has (n-1) edges, where n is the number of vertices.