You are viewing a single comment's thread. Return to all comments →
Kruskal's Algorithm for Finding Minimum Spanning Tree (MST):
For proper understing of the code below, please read Disjoint Set Data Structure (Union Find, Rank and Path compression)
def find(parent, val): if parent[val - 1] != val: parent[val - 1] = find(parent, parent[val - 1]) return parent[val - 1] def apply_union(parent, rank, x, y): if rank[x - 1] < rank[y - 1]: parent[x - 1] = y elif rank[x - 1] > rank[y - 1]: parent[y - 1] = x else: parent[y - 1] = x rank[x - 1] += 1 def kruskals(g_nodes, g_from, g_to, g_weight): graph = list(zip(g_from, g_to, g_weight)) graph = sorted(graph, key=lambda val: val[2]) e = 0 result = [] parent = list(range(1, g_nodes + 1)) rank = [0] * g_nodes for i, (u, v, w) in enumerate(graph): x = find(parent, u) y = find(parent, v) if x != y: apply_union(parent, rank, x, y) result.append((u, v, w)) e += 1 return result
Seems like cookies are disabled on this browser, please enable them to open this website
Kruskal (MST): Really Special Subtree
You are viewing a single comment's thread. Return to all comments →
Kruskal's Algorithm for Finding Minimum Spanning Tree (MST):
For proper understing of the code below, please read Disjoint Set Data Structure (Union Find, Rank and Path compression)