(G, s)
| 213 | |
| 214 | |
| 215 | def prim(G, s): |
| 216 | dist, known, path = {s: 0}, set(), {s: 0} |
| 217 | while True: |
| 218 | if len(known) == len(G) - 1: |
| 219 | break |
| 220 | mini = 100000 |
| 221 | for i in dist: |
| 222 | if i not in known and dist[i] < mini: |
| 223 | mini = dist[i] |
| 224 | u = i |
| 225 | known.add(u) |
| 226 | for v in G[u]: |
| 227 | if v[0] not in known: |
| 228 | if v[1] < dist.get(v[0], 100000): |
| 229 | dist[v[0]] = v[1] |
| 230 | path[v[0]] = u |
| 231 | |
| 232 | |
| 233 | """ |