Description

Offline Assignment 4

Section A1, A2, B2:
You have to implement the Kruskal’s minimum spanning tree algorithm for an undirected weighted graph G = (V, E) as the fourth offline assignment of CSE 208. Please consider the following requirements:
1) Implement necessary code for graph representation without using standard template libraries.
2) Make sure the running time of the algorithm is O (E lg V).
3) Use file operations for input and output.

Sample Input Sample Output

10 16
0 1 4
0 7 8
1 7 10
1 2 8
2 3 7
2 8 2
2 5 3
5 6 2
6 7 1
8 6 6
3 5 15
3 4 10
4 5 10
7 8 8
9 7 2
9 5 1

Added edges: [edges can vary]
(6, 7)
(9, 5)
(2, 8)
(5, 6)
(2, 5)
(0, 1)
(2, 3)
(0, 7)
(3, 4)

MST weight: 38

Section B1:
You have to implement the Prim’s minimum spanning tree algorithm for an undirected weighted graph G = (V, E) as the fourth offline assignment of CSE 208. Please consider the following requirements:
1) Implement necessary code for graph representation without using standard template libraries.
2) Make sure the running time of the algorithm is O (V lg V).
3) Use file operations for input and output.

Sample Input Sample Output

10 16
0 1 4
0 7 8
1 7 10
1 2 8
2 3 7
2 8 2
2 5 3
5 6 2
6 7 1
8 6 6
3 5 15
3 4 10
4 5 10
7 8 8
9 7 2
9 5 1

Added edges: [edges can vary]
(0, 1)
(1, 2)
(2, 8)
(2, 5)
(9, 5)
(5, 6)
(6, 7)
(2, 3)
(5, 4)

MST weight: 38