Performs Borůvka's algorithm to find MST.
(self)
| 81 | self.set_component(v_node) |
| 82 | |
| 83 | def boruvka(self) -> None: |
| 84 | """Performs Borůvka's algorithm to find MST.""" |
| 85 | |
| 86 | # Initialize additional lists required to algorithm. |
| 87 | component_size = [] |
| 88 | mst_weight = 0 |
| 89 | |
| 90 | minimum_weight_edge: list[Any] = [-1] * self.m_num_of_nodes |
| 91 | |
| 92 | # A list of components (initialized to all of the nodes) |
| 93 | for node in range(self.m_num_of_nodes): |
| 94 | self.m_component.update({node: node}) |
| 95 | component_size.append(1) |
| 96 | |
| 97 | num_of_components = self.m_num_of_nodes |
| 98 | |
| 99 | while num_of_components > 1: |
| 100 | for edge in self.m_edges: |
| 101 | u, v, w = edge |
| 102 | |
| 103 | u_component = self.m_component[u] |
| 104 | v_component = self.m_component[v] |
| 105 | |
| 106 | if u_component != v_component: |
| 107 | """If the current minimum weight edge of component u doesn't |
| 108 | exist (is -1), or if it's greater than the edge we're |
| 109 | observing right now, we will assign the value of the edge |
| 110 | we're observing to it. |
| 111 | |
| 112 | If the current minimum weight edge of component v doesn't |
| 113 | exist (is -1), or if it's greater than the edge we're |
| 114 | observing right now, we will assign the value of the edge |
| 115 | we're observing to it""" |
| 116 | |
| 117 | for component in (u_component, v_component): |
| 118 | if ( |
| 119 | minimum_weight_edge[component] == -1 |
| 120 | or minimum_weight_edge[component][2] > w |
| 121 | ): |
| 122 | minimum_weight_edge[component] = [u, v, w] |
| 123 | |
| 124 | for edge in minimum_weight_edge: |
| 125 | if isinstance(edge, list): |
| 126 | u, v, w = edge |
| 127 | |
| 128 | u_component = self.m_component[u] |
| 129 | v_component = self.m_component[v] |
| 130 | |
| 131 | if u_component != v_component: |
| 132 | mst_weight += w |
| 133 | self.union(component_size, u_component, v_component) |
| 134 | print(f"Added edge [{u} - {v}]\nAdded weight: {w}\n") |
| 135 | num_of_components -= 1 |
| 136 | |
| 137 | minimum_weight_edge = [-1] * self.m_num_of_nodes |
| 138 | print(f"The total weight of the minimal spanning tree is: {mst_weight}") |
| 139 | |
| 140 |