Alternative Minimum Spanning Tree Algorithms Each of the following three algorithms takes a connected graph and a weight function as input and returns a set of edges T. For each algorithm, either prove (use logical arguments) or disapprove (by giving a counter example) that T is a minimum spanning tree. Describe (no pseudo code) the most efficient implementation of each algorithm, whether or not it computes a minimum spanning tree. 1. Maybe-MST-A(G, w) 1 sort the edges into non-increasing order of edge weight w 2 T = E 3 for each edge e, taken in non-increasing order by weight 4 if T – {e} is a connected gr
Alternative Minimum Spanning Tree Algorithms
Each of the following three algorithms takes a connected graph and a weight function as input and returns a set of edges T. For each
1.
Maybe-MST-A(G, w)
1 sort the edges into non-increasing order of edge weight w
2 T = E
3 for each edge e, taken in non-increasing order by weight
4 if T – {e} is a connected graph
5 T = T – {e}
6 return T
2.
Maybe-MST-B(G, w)
1 T = ∅
2 for each edge e, taken in arbitrary order
3 if T ∪ {e} has no cycles
4 T = T ∪{e}
5 return T
3.)
Maybe-MST-C(G, w)
1 T = ∅
2 for each edge e, taken in arbitrary order
3 T = T ∪{e}
4 if T ∪ {e} has a cycle c
5 let e* be a maximum-weight edge on c
6 T = T −{e*}
7 return T
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
