Implementation of Boruvka's algorithm >>> g = Graph() >>> g = Graph.build([0, 1, 2, 3], [[0, 1, 1], [0, 2, 1],[2, 3, 1]]) >>> g.distinct_weight() >>> bg = Graph.boruvka_mst(g) >>> print(bg) 1 -> 0 == 1 2 -> 0 == 2 0 ->
(graph)
| 148 | |
| 149 | @staticmethod |
| 150 | def boruvka_mst(graph): |
| 151 | """ |
| 152 | Implementation of Boruvka's algorithm |
| 153 | >>> g = Graph() |
| 154 | >>> g = Graph.build([0, 1, 2, 3], [[0, 1, 1], [0, 2, 1],[2, 3, 1]]) |
| 155 | >>> g.distinct_weight() |
| 156 | >>> bg = Graph.boruvka_mst(g) |
| 157 | >>> print(bg) |
| 158 | 1 -> 0 == 1 |
| 159 | 2 -> 0 == 2 |
| 160 | 0 -> 1 == 1 |
| 161 | 0 -> 2 == 2 |
| 162 | 3 -> 2 == 3 |
| 163 | 2 -> 3 == 3 |
| 164 | """ |
| 165 | num_components = graph.num_vertices |
| 166 | |
| 167 | union_find = Graph.UnionFind() |
| 168 | mst_edges = [] |
| 169 | while num_components > 1: |
| 170 | cheap_edge = {} |
| 171 | for vertex in graph.get_vertices(): |
| 172 | cheap_edge[vertex] = -1 |
| 173 | |
| 174 | edges = graph.get_edges() |
| 175 | for edge in edges: |
| 176 | head, tail, weight = edge |
| 177 | edges.remove((tail, head, weight)) |
| 178 | for edge in edges: |
| 179 | head, tail, weight = edge |
| 180 | set1 = union_find.find(head) |
| 181 | set2 = union_find.find(tail) |
| 182 | if set1 != set2: |
| 183 | if cheap_edge[set1] == -1 or cheap_edge[set1][2] > weight: |
| 184 | cheap_edge[set1] = [head, tail, weight] |
| 185 | |
| 186 | if cheap_edge[set2] == -1 or cheap_edge[set2][2] > weight: |
| 187 | cheap_edge[set2] = [head, tail, weight] |
| 188 | for head_tail_weight in cheap_edge.values(): |
| 189 | if head_tail_weight != -1: |
| 190 | head, tail, weight = head_tail_weight |
| 191 | if union_find.find(head) != union_find.find(tail): |
| 192 | union_find.union(head, tail) |
| 193 | mst_edges.append(head_tail_weight) |
| 194 | num_components = num_components - 1 |
| 195 | mst = Graph.build(edges=mst_edges) |
| 196 | return mst |