julia - 具有邻接矩阵的 julia 中的 prim 算法

Question

我正在尝试在 julia 中实现 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

我想我必须以这样的形式“ reshape ”我的矩阵 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实现了这个算法。您可以找到代码 here .

我还对您的算法做了一些注释，以使其正常工作，并在不改变其总体结构的情况下指出了潜在的改进:

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