Problem 1: We have seen Kruskal\'s Algorithm and Prim\'s Algorithm, two greedy a
ID: 3809075 • Letter: P
Question
Problem 1: We have seen Kruskal's Algorithm and Prim's Algorithm, two
greedy algorithms for building minimum spanning trees. Both of these algo-
rithms begin with zero edges, and then add edges in a speci c order one at
a time until a spanning tree is created.
One can also create a minimum spanning tree by removing edges one at a
time, in a greedy manner, from the input graph G. In other words, your
initial edgeset should contain all edges in G, and you should greedily remove
edges from this set until you are left with a minimum spanning tree.
Describe this greedy algorithm in sucient detail for me to implement it.
Explanation / Answer
Please find the algorithm below :
Initialize E with the set of all edges in G
Initialize T with E (* T will store edges of a MST *)
while E is not empty do
choose i E of largest cost
if removing i does not disconnect T then
remove i from T
endif
done
return the set T
let me know if you are not able to get anything.