时间戳

首页 > 解决方案 > 具有邻接矩阵的Julia中的prim算法

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

问题描述

我试图在 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

我想我必须以这样的形式“重塑”我的矩阵 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
]]

但也有了这个，我得到了同样的错误。

标签： julia

解决方案

首先注意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

推荐阅读