Algorithm: Algorithm Kruskal(E, cost, n, t) { Construct a heap out of the edge costs using Heapify; for i:=1 to n, do parent[i]:=—1; i := O; mincost := 0.0; while ( (i < n — 1) and (heap not empty)) do { Delete a minimum cost edge (u, v) from the heap and reheapify using Adjust; j:=Find(u); k := Find(v); if (j!=k) then { i:=i+1; t[i, 1] := u; t[i, 2]:=v; mincost := mincost + cost[u, v]; Union(j, k); } } if (i != n — 1) then write ("No spanning tree"); else return mincost; } Source Code: def kruskal(E, cost, n): # E is the edge set, cost is the cost matrix, n is the number of vertices T = [] # T is the set of edges in the tree S = [] # S is the set of vertices in the tree while len(T) < n ...
Comments
Post a Comment