Lots of Prim's algorithm implementations seem long, and rely on a priority queue implementation.

If I use an adjacency matrix I can then calculate the next item to take using functional programming in Swift.

func prims (_ matrix : [[Int]]) {
    var selected = 0
    var selectedSoFar = Set<Int>()
    selectedSoFar.insert( (matrix[selected].enumerated().min{ $0.element < $1.element }?.offset)! )

    while selectedSoFar.count < matrix.count {
        var minValue = Int.max
        var minIndex = selected
        var initialRow = 0
        for row in selectedSoFar {
            let candidateMin = matrix[row].enumerated().filter{$0.element > 0 && !selectedSoFar.contains($0.offset) }.min{ $0.element < $1.element }
            if (minValue > candidateMin?.element ?? Int.max ) {
                minValue = candidateMin?.element ?? Int.max
                minIndex = (candidateMin?.offset) ?? 0
                initialRow = row
        print ("edge value \(minValue) with \(initialRow) to \(minIndex)")
        selected = (minValue)

let input = [[0,9,75,0,0],[9,0,95,19,42],[75,95,0,51,66],[0,19,51,0,31],[0,42,66,31,0]]

Essentially is there anything "wrong" with this implementation? This is not homework, my code runs correctly for the included output, I've stepped through the output with pen and paper, and I appreciate this is faster if I use an adjacency list. However the Ray Wenderlich implementation of Prims uses 7 files and >200 lines of code. Am I missing something?


1 Answer 1


Am I missing something?

Each expansion of the tree visits every vertex, either as a member of selectedSoFar or as a candidate in matrix[row]. That makes the runtime \$O(n^2)\$ in the number of vertices.

An algorithm based on ordered data will tend toward \$O(n*log(n))\$. With a million vertices, that's 50 thousand times faster—the difference between an hour and six years.

See also Wikipedia on Prim's; there's a section on time complexity.

  • \$\begingroup\$ "I appreciate this is faster if I use an adjacency matrix" should have read " appreciate this is faster if I use an adjacency list". \$\endgroup\$ Commented Mar 21, 2019 at 5:54
  • 3
    \$\begingroup\$ Understood, but you're asking why it isn't done this way, and that's why. It's not slower as in "hey this is kind of slow," it's slower as in "hey this was started when I was born and has yet to complete." \$\endgroup\$ Commented Mar 21, 2019 at 6:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.