Prim's Algorithm with min heap. Runtime: O((m + n)log n) with `m` edges and `n` vertices Yield: Edges of a Minimum Spanning Tree Usage: prim(graph, graph[0])
(graph: list, root: Vertex)
| 84 | |
| 85 | |
| 86 | def prim_heap(graph: list, root: Vertex) -> Iterator[tuple]: |
| 87 | """Prim's Algorithm with min heap. |
| 88 | |
| 89 | Runtime: |
| 90 | O((m + n)log n) with `m` edges and `n` vertices |
| 91 | |
| 92 | Yield: |
| 93 | Edges of a Minimum Spanning Tree |
| 94 | |
| 95 | Usage: |
| 96 | prim(graph, graph[0]) |
| 97 | """ |
| 98 | for u in graph: |
| 99 | u.key = math.inf |
| 100 | u.pi = None |
| 101 | root.key = 0 |
| 102 | |
| 103 | h = list(graph) |
| 104 | hq.heapify(h) |
| 105 | |
| 106 | while h: |
| 107 | u = hq.heappop(h) |
| 108 | for v in u.neighbors: |
| 109 | if (v in h) and (u.edges[v.id] < v.key): |
| 110 | v.pi = u |
| 111 | v.key = u.edges[v.id] |
| 112 | hq.heapify(h) |
| 113 | |
| 114 | for i in range(1, len(graph)): |
| 115 | yield (int(graph[i].id) + 1, int(graph[i].pi.id) + 1) |
| 116 | |
| 117 | |
| 118 | def test_vector() -> None: |