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.

• WishIHadThreeGuns: "I appreciate this is faster if I use an adjacency matrix" should have read " appreciate this is faster if I use an adjacency list".
• Oh My Goodness: 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."