Assignment-3 (25 August 2015)

An important application of Greedy Strategy: Computation of Minimum Spanning Tree (MST)

In order to appreciate application of MST's read

MST's in Financial Markets

Implement Kruskal's algorithm for finding MST of a given graph. Write pseudocode of the algorithm which includes functions

Find_Min (L) and If_Cycle(PT, edge).

Find_Min(L) finds minimum weighted element of the List L and If_Cycle(PT, edge) outputs 1 if edge can be added to the partial tree/forest, PT without forming a cycle, otherwise 0.

The program should output the MST as well as its weight. Write the code in a modular fashion so that Find_Min(L) can be implemented using different algorithms like ordered list; Select-Min; or with a heap implementation.

The graph is read from a file with first line containing the number of nodes in the graph and next line onwards, the edge list in the format

node node weight (tab separated)

small test file