Returns the edges that make up the minimum spanning tree Parameters ---------- G : graph weighted graph Returns ------- result_dict : dict the edges that make up the minimum spanning tree Examples -------- Returns the edges that make up the mini
(G, weight="weight")
| 146 | @only_implemented_for_UnDirected_graph |
| 147 | @hybrid("cpp_Kruskal") |
| 148 | def Kruskal(G, weight="weight"): |
| 149 | """Returns the edges that make up the minimum spanning tree |
| 150 | |
| 151 | Parameters |
| 152 | ---------- |
| 153 | G : graph |
| 154 | weighted graph |
| 155 | |
| 156 | Returns |
| 157 | ------- |
| 158 | result_dict : dict |
| 159 | the edges that make up the minimum spanning tree |
| 160 | |
| 161 | Examples |
| 162 | -------- |
| 163 | Returns the edges that make up the minimum spanning tree |
| 164 | |
| 165 | >>> Kruskal(G,weight="weight") |
| 166 | |
| 167 | """ |
| 168 | adj = G.adj.copy() |
| 169 | result_dict = {} |
| 170 | edge_list = [] |
| 171 | for i in G: |
| 172 | result_dict[i] = {} |
| 173 | for i in G: |
| 174 | for j in G[i]: |
| 175 | wt = adj[i][j].get(weight, 1) |
| 176 | edge_list.append([i, j, wt]) |
| 177 | edge_list.sort(key=lambda a: a[2]) |
| 178 | group = [[i] for i in G] |
| 179 | for edge in edge_list: |
| 180 | for i in range(len(group)): |
| 181 | if edge[0] in group[i]: |
| 182 | m = i |
| 183 | if edge[1] in group[i]: |
| 184 | n = i |
| 185 | if m != n: |
| 186 | result_dict[edge[0]][edge[1]] = edge[2] |
| 187 | group[m] = group[m] + group[n] |
| 188 | group[n] = [] |
| 189 | return result_dict |
| 190 | |
| 191 | |
| 192 | @not_implemented_for("multigraph") |