Consider a undirected graph, G(N,A), where N and A are the set of nodes and arcs (edges), respectively. Associated with each arc (i,j) in A is a cost c(i,j). Let |N| = n and |A|=m. The problem is to find a rooted undirected spanning tree, G(N,S) where S is a subset of A such that the sum of c(i,j) for all (i,j) in S is minimized. The rooted undirected spanning tree is defined as a graph which connects, without any cycle, all nodes with n-1 arcs, i.e., each node, except the root, has one and only one incoming arc.
You are required to read a graph from a text file. The first 2 numbers (N and E) in the text file specifies the number of vertices and the number of edges available. Follows are the E lines each specifying a link between 2 nodes.
The problem is to find a minimum spanning tree.
Sample input:
8 10
0 1 9
1 3 7
2 3 15
3 4 10
4 6 8
4 5 3
5 6 14
1 6 5
6 7 6
1 7 12
Sample output (The sum of the weights of the spanning tree edges)
53