IITKESO207SPA3E - Maybe a Minimum Spanning Tree
Given a connected graph G = (V,E) with non-negative edge weights, here is a different way to construct an MST greedily by deleting edges instead of adding edges. The basic idea is as follows :
- E' = E
Pick any cycle in G, find the heaviest edge, delete it from the set E'
Until E' is an MST.
You have to conver the basic diea into a proper algorithm.
The input will have in one line, an integer n. This will represent the number of nodes in the tree. The remaining lines will denote the edges in the graph, one edge per each line. The format of the edges will be of the form i j w, three space separated integers denoting the start vertex, the end vertex, and the edge weight of the edge.
Your output must contain all the edges in your MST created using the above algorithm . It must have one edge per line, ordered in increasing order of the first node, then the second node.
1 2 5
2 3 3
1 5 1
2 4 2
4 5 6
9 8 1
5 7 7
1 6 3
8 6 5
9 5 4
Note 1 : The test case had a flaw in it, which caused many students to obtain 80/100. It has been updated since then, please resubmit your solutions.
It should be clear whether graph is directed or undirected....!