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 - 1:

min_cost = float('inf') for i in range(len(E)):

if cost[E[i][0]][E[i][1]] < min_cost:

min_cost = cost[E[i][0]][E[i][1]] min_edge = E[i]

if min_edge[0] not in S or min_edge[1] not in S: T.append(min_edge)

S.append(min_edge[0]) S.append(min_edge[1])

E.remove(min_edge) return T

E = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

[100, 6, 4, 0]]

n = 4

print(kruskal(E, cost, n))