(g, s)
| 282 | |
| 283 | |
| 284 | def prim(g, s): |
| 285 | dist, known, path = {s: 0}, set(), {s: 0} |
| 286 | while True: |
| 287 | if len(known) == len(g) - 1: |
| 288 | break |
| 289 | mini = 100000 |
| 290 | for key, value in dist.items(): |
| 291 | if key not in known and value < mini: |
| 292 | mini = value |
| 293 | u = key |
| 294 | known.add(u) |
| 295 | for v in g[u]: |
| 296 | if v[0] not in known and v[1] < dist.get(v[0], 100000): |
| 297 | dist[v[0]] = v[1] |
| 298 | path[v[0]] = u |
| 299 | return dist |
| 300 | |
| 301 | |
| 302 | """ |