Advertisement
Guest User

Untitled

a guest
Jun 25th, 2019
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.59 KB | None | 0 0
  1. function prims(AD)
  2.  
  3.  
  4. n = size(AD)
  5. n1 = n[1]
  6.  
  7.  
  8. # choose initial vertex from graph
  9. vertex = 1
  10.  
  11. # initialize empty edges array and empty MST
  12. MST = []
  13. edges = []
  14. visited = []
  15. minEdge = [nothing, nothing, float(Inf)]
  16.  
  17. # run prims algorithm until we create an MST
  18. # that contains every vertex from the graph
  19. while length(MST) != n1 - 1
  20.  
  21. # mark this vertex as visited
  22. append!(visited, vertex)
  23.  
  24. # add each edge to list of potential edges
  25. for r in 1:n1
  26. if AD[vertex][r] != 0
  27. append!(edges, [vertex, r, AD[vertex][r]])
  28. end
  29. end
  30. # find edge with the smallest weight to a vertex
  31. # that has not yet been visited
  32. for e in 1:length(edges)
  33. if edges[e][3] < minEdge[3] && edges[e][2] not in visited
  34. minEdge = edges[e]
  35. end
  36. end
  37. # remove min weight edge from list of edges
  38. deleteat!(edges, minEdge)
  39.  
  40. # push min edge to MST
  41. append!(MST, minEdge)
  42.  
  43. # start at new vertex and reset min edge
  44. vertex = minEdge[2]
  45. minEdge = [nothing, nothing, float(Inf)]
  46. end
  47.  
  48. return MST
  49.  
  50. end
  51.  
  52. C = [0 2 3 0 0 0; 2 0 5 3 4 0; 3 5 0 0 4 0; 0 3 0 0 2 3; 0 4 4 2 0 5; 0 0 0 3 5 0]
  53.  
  54. ERROR: BoundsError
  55. Stacktrace:
  56. [1] getindex(::Int64, ::Int64) at .number.jl:78
  57. [2] prims(::Array{Int64,2}) at .untitled-8b8d609f2ac8a0848a18622e46d9d721:70
  58. [3] top-level scope at none:0
  59.  
  60. D = [ [0,2,3,0,0,0], [2,0,5,3,4,0], [3,5,0,0,4,0], [0,3,0,0,2,3], [0,4,4,2,0,5], [0,0,0,3,5,0
  61. ]]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement