Suppose you are a manager in the IT department for the government of a corrupt dictator, who has a collection of computers that need to be connected together to create a communication network for his spies.
You are given a weighted graph, G, such that each vertex in G is one of these computers and each edge in G is a pair of computers that could be connected with a communication line. It is your job to decide how to connect the computers.
Suppose now that the CIA has approached you and is willing to pay you various amounts of money for you to choose some of these edges to belong to this network (presumably so that they can spy on the dictator).
Thus, for you, the weight of each edge in G is the amount of money, in U.S. dollars, that the CIA will pay you for using that edge in the communication network.
Implement an efficient algorithm, therefore, for finding a maximum spanning tree in G, which would maximize the money you can get from the CIA for connecting the dictator's computers in a spanning tree. What is the running time of your algorithm?
Your program will take as input a file with edge information. Each line in the file contains from, to and weight. You may assume the vertices are numbered from 0 to N. The weights are unique and non-negative. It will construct the Graph and print the edges in the maximum spanning tree.