| 405 | return self.prim(nodes, edges) |
| 406 | |
| 407 | def prim(self, nodes, edges): |
| 408 | conn = defaultdict( list ) |
| 409 | for n1,n2,c in edges: # makes graph undirected |
| 410 | conn[ n1 ].append( (c, n1, n2) ) |
| 411 | conn[ n2 ].append( (c, n2, n1) ) |
| 412 | |
| 413 | mst = [] |
| 414 | used = set() |
| 415 | used.add( nodes[0] ) |
| 416 | usable_edges = conn[ nodes[0] ][:] |
| 417 | heapify( usable_edges ) |
| 418 | |
| 419 | while usable_edges: |
| 420 | cost, n1, n2 = heappop( usable_edges ) |
| 421 | if n2 not in used: |
| 422 | used.add( n2 ) |
| 423 | mst.append( ( n1, n2, cost ) ) |
| 424 | |
| 425 | for e in conn[ n2 ]: |
| 426 | if e[ 2 ] not in used: |
| 427 | heappush( usable_edges, e ) |
| 428 | return mst |
| 429 | |
| 430 | """ |
| 431 | Kruskals begins with forest and merge into a tree |