Swift Prim's algorithm

Question

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)")
        selectedSoFar.insert(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]]
prims(input)

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?

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.