Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- function prims(AD)
- n = size(AD)
- n1 = n[1]
- # choose initial vertex from graph
- vertex = 1
- # initialize empty edges array and empty MST
- MST = []
- edges = []
- visited = []
- minEdge = [nothing, nothing, float(Inf)]
- # run prims algorithm until we create an MST
- # that contains every vertex from the graph
- while length(MST) != n1 - 1
- # mark this vertex as visited
- append!(visited, vertex)
- # add each edge to list of potential edges
- for r in 1:n1
- if AD[vertex][r] != 0
- append!(edges, [vertex, r, AD[vertex][r]])
- end
- end
- # find edge with the smallest weight to a vertex
- # that has not yet been visited
- for e in 1:length(edges)
- if edges[e][3] < minEdge[3] && edges[e][2] not in visited
- minEdge = edges[e]
- end
- end
- # remove min weight edge from list of edges
- deleteat!(edges, minEdge)
- # push min edge to MST
- append!(MST, minEdge)
- # start at new vertex and reset min edge
- vertex = minEdge[2]
- minEdge = [nothing, nothing, float(Inf)]
- end
- return MST
- end
- 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]
- ERROR: BoundsError
- Stacktrace:
- [1] getindex(::Int64, ::Int64) at .number.jl:78
- [2] prims(::Array{Int64,2}) at .untitled-8b8d609f2ac8a0848a18622e46d9d721:70
- [3] top-level scope at none:0
- 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
- ]]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement