Consider the following variant of the Minimum Spanning Tree
(MST) problem. We are given an undirected graph G = (V, E) with n
vertices (numbered from 0 to n − 1) and m edges, a positive
(not necessarily unique)edge cost ce for each edge
in E. and a subset of edges A⊂E (note that A may contain cycles). Suppose that E represents a set of possible direct fibre links between vertices and A represents the
existing set of direct fibre links between vertices. We would like to find the cheapest
way to connect all the vertices into one connected network.
The abstract problem we are interested in solving is to find a subset X ⊆E A of edges of minimum cost such that (V,X cup A) is connected. Task: Design an algorithm that solves this problem in O (m log n)time.Implement your algorithm (in Ed) and test it on the following instances: Graph 8,Graph 250, Graph 1000.
Each instance is given in a text file as described in Question
1.
Each graph instance is given in a text file using the following format
where a is the number of edges in A.