Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Write a program that finds a minimum spanning tree of a given weighted graph. The input to the program is a file containing a weighted graph. The input file has the following format. The first line specifies the number of vertices in the graph. The second line specifies the number of edges in the graph. Each subsequent line contains on edge. One edge is specified by the two vertices of the edge and the weight of the edge separated by spaces. The vertices are numbered 1,2,3,... The edge weights are real numbers. The program finds a minimum spanning tree and writes the results to an output file. The output file has the following format. The first line specifies the total edge length of the minimum spanning tree. Each subsequent line contains one edge of the minimum spanning tree. One edge is specified by the two vertices of the edge and the length of the edge separated by spaces. The program must be based off the given pseudocode.
- pseudocode:
- - edge array P vertex array Q
- 1 2 1 _ _ _ _ _ _
- 2 3 3 _ 1 2 3 4 5
- 1 4 4 _
- 2 4 1 _
- 2 5 2 _
- 3 5 2 _
- 4 5 3 _
- - prims minimum spanning tree algorithm
- -in array P, mark all the edges as not chosen
- in array Q, mark all vertices as not visited
- in array Q, choose a vertex and mark it as visited
- - repeat vertices (n-1) times
- {
- -in array P, find a least cost edge uv between a visited vertex u and an unvisited vertex v that has not yet been chosen (requires
- a single loop through array P)
- -mark v as visited in array Q
- -mark edge uv as chosen in array P
- }
- example input file-
- 5
- 7
- 1 2 1
- 1 4 4
- 2 3 3
- 2 4 1
- 2 5 2
- 3 5 2
- 4 5 3
- example output file-
- 6
- 1 2 1
- 2 4 1
- 2 5 2
- 3 5 2
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement