4
\$\begingroup\$

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?

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\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\$ – WishIHadThreeGuns Mar 21 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\$ – Oh My Goodness Mar 21 at 6:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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