Advertisement
samham1218

prims algorithm

Nov 17th, 2018
378
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.74 KB | None | 0 0
  1. 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.
  2.  
  3. pseudocode:
  4.  
  5. - edge array P vertex array Q
  6. 1 2 1 _ _ _ _ _ _
  7. 2 3 3 _ 1 2 3 4 5
  8. 1 4 4 _
  9. 2 4 1 _
  10. 2 5 2 _
  11. 3 5 2 _
  12. 4 5 3 _
  13.  
  14. - prims minimum spanning tree algorithm
  15. -in array P, mark all the edges as not chosen
  16. in array Q, mark all vertices as not visited
  17. in array Q, choose a vertex and mark it as visited
  18.  
  19. - repeat vertices (n-1) times
  20. {
  21. -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
  22. a single loop through array P)
  23. -mark v as visited in array Q
  24. -mark edge uv as chosen in array P
  25. }
  26.  
  27.  
  28.  
  29. example input file-
  30. 5
  31. 7
  32. 1 2 1
  33. 1 4 4
  34. 2 3 3
  35. 2 4 1
  36. 2 5 2
  37. 3 5 2
  38. 4 5 3
  39.  
  40. example output file-
  41. 6
  42. 1 2 1
  43. 2 4 1
  44. 2 5 2
  45. 3 5 2
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement