# Swift Prim's algorithm

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?

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.