Assignment 4. Minimum spanning tree
Completion requirements
Opened: Tuesday, 18 April 2023, 12:00 AM
Develop a program that searches for a MST of a given weighted graph. You should implement one of the two algorithms.
•Kruskal’s
algorithm. For implementing Union-Find data structure you will get 3 additional
points.
•Prim’s
algorithm with std::priority_queue data structure.
Input file (text format):
•The
1st line: names of vertices, separated by spaces.
•Other
lines contain edges and their weights.
Each line describes one edge as two incident vertices together with the edge’s
weight, separated by space. Weights are fixed point decimal numbers; they
should be represented with float numeric values.
Output file (text format):
For a graph with n vertices the output file should contain n lines.
The first line represents the total weight of the MST and the other lines represent edges of the MST.- 18 April 2023, 9:04 PM
- 18 April 2023, 9:04 PM
- 18 April 2023, 9:04 PM