Question

SPANNING TREE AND GRAPH C++ (use explanation and visualization if needed) and also provide an algorithm

Do not need to provide code or a description of the algorithm in that case.

Let G be a simple, undirected graph with positive integer edge weights. Suppose we want to find the maximum spanning tree of G. That is, of all spanning trees of G, we want the one with the highest total edge weight. If there are multiple, any one of them is fine to find.

Describe a simple algorithm to accomplish this.

Answer 1

Hi,

We can use, the opposite of Kruskal's algorithm for minimum spanning tree by choosing max edge weight in every step.

Kruskal's Algorithm for MAXIMUM Spanning tree:

1. Sort all the edges in decreasing order(MAX to MIN) of their edge weights/costs.
2. Pick the maximum cost edge.
3. Check if it forms a cycle with the spanning tree formed so far.
   1. If cycle is not formed, include this edge.
   2. Else, discard it. Go to step 2 until there are (V-1) edges in the spanning tree.

Example: