Prim's Algorithm
- Given an undirected, connected and weighted graph G(V, E) with V number of vertices (which are numbered from 0 to V-1) and E number of edges.
- Find and print the Minimum Spanning Tree (MST) using Prim's algorithm.
- For printing MST follow the steps -
- In one line, print an edge which is part of MST in the format -
- v1 v2 w
- where, v1 and v2 are the vertices of the edge which is included in MST and whose weight is w. And v1 <= v2 i.e. print the smaller vertex first while printing an edge.
- Print V-1 edges in above format in different lines.
- Note : Order of different edges doesn't matter.
Input Format
- Line 1: Two Integers V and E (separated by space)
- Next E lines : Three integers ei, ej and wi, denoting that there exists an edge between vertex ei and vertex ej with weight wi (separated by space)
Constraints
- 2 <= V, E <= 10^5
- 1 <= Wi <= 10^5
- Time Limit: 1 sec
Output Format
- Print the MST, as described in the task.
Sample Input 0
4 4
0 1 3
0 3 5
1 2 1
2 3 8
Sample Output 0
0 1 3
1 2 1
0 3 5
Sample Input 1
3 3
1 2 6
2 0 2
1 0 2
Sample Output 1
0 1 2
0 2 2
xxxxxxxxxx1
with Ada.Text_IO, Ada.Integer_Text_IO;2
use Ada;3
4
procedure Solution is5
-- Enter your code here. Read input from STDIN. Print output to STDOUT6
7
8
end Solution