Swift Prim's algorithm
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.