алгоритм Прима в юлии с матрицей смежности

Question

Я пытаюсь реализовать алгоритм Prim в Юлии.

Моя функция получает матрицу смежности с весами, но работает неправильно.Я не знаю, что я должен изменить.Я полагаю, есть некоторая проблема с функцией append! ().

Может быть, есть другой / лучший способ реализовать алгоритм, просто передавая матрицу смежности?

Спасибо.

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

Я думаю, мне нужно "изменить" мою Матрицу C в такую ​​форму, как эта

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
]]

Но и с этим я получаю ту же ошибку.

Answer 1

Первое замечание: LightGraphs.jl имеет этот алгоритм реализован. Вы можете найти код здесь .

Я также сделал несколько замечаний по вашему алгоритму, чтобы он работал и указал потенциальные улучшения без изменения его общей структуры:

using DataStructures # library defining PriorityQueue type

function prims(AD::Matrix{T}) where {T<:Real} # make sure we get what we expect
    # make sure the matrix is symmetric
    @assert transpose(AD) == AD
    n1 = size(AD, 1)
       vertex = 1
    # it is better to keep edge information as Tuple rather than a vector
    # also note that I add type annotation for the collection to improve speed
    # and make sure that the stored edge weight has a correct type
    MST = Tuple{Int, Int, T}[]
    # using PriorityQueue makes the lookup of the shortest edge fast
    edges = PriorityQueue{Tuple{Int, Int, T}, T}()
    # we will eventually visit almost all vertices so we can use indicator vector
    visited = falses(n1)
    while length(MST) != n1 - 1
        visited[vertex] = true
        for r in 1:n1
            # you access a matrix by passing indices separated by a comma
            dist = AD[vertex, r]
            # no need to add edges to vertices that were already visited
            if dist != 0 && !visited[r]
                edges[(vertex, r, dist)] = dist
            end
        end
        # we will iterate till we find an unvisited destination vertex
        while true
            # handle the case if the graph was not connected
            isempty(edges) && return nothing
            minEdge = dequeue!(edges)
            if !visited[minEdge[2]]
                # use push! instead of append!
                push!(MST, minEdge)
                vertex = minEdge[2]
                break
            end
        end
    end
    return MST
end