Kruskal's minimum spanning tree

Given a weighted, undirected graph as an edge list and the number of vertices, find a minimum spanning tree without creating cycles.

The strategy to implement the Kruskal algorithm using Union-Find is given below:

• Sort all the edges of a graph according to their edge-weight values.
• Create three distinct sets to maintain nodes of a graph, their hierarchy in a tree, and corresponding ranks for every node. Primarily, all rank values should be initialized to 0 and parent values to -1 (representing each node as its own tree itself).
• For each insertion of an edge in MST, update the rank and parent of each node. Do not insert the edge connecting two nodes if they have the same parent node, as this will cause a cycle in the tree structure.

• Python
• Javascript
•  Run

def find(parent, i):
  if parent[i] != i:
    parent[i] = find(parent, parent[i])
  
  return parent[i]

def union(parent, rank, x, y):
  if rank[x] < rank[y]:
    parent[x] = y
  elif rank[x] > rank[y]:
    parent[y] = x
  else:
    parent[y] = x
    rank[x] += 1

def kruskal(edges, V):
  result = []

  edges = sorted(edges, key=lambda item: item[2])
  parent = [node for node in range(V)]
  rank = [0 for _ in range(V)]
  
  i = 0

  while len(result) < V - 1:
    u, v, w = edges[i]
    i = i + 1
    x = find(parent, u)
    y = find(parent, v)

    if x != y:
      result.append([u, v, w])
      union(parent, rank, x, y)

  return result

V = 5
edges = [
  [0, 1, 1],
  [2, 4, 2],
  [0, 2, 3],
  [1, 2, 3],
  [2, 3, 4],
  [3, 4, 5],
  [1, 3, 6]
]

print(kruskal(edges, V))

//=include kruskal.js