Before Kruskal

Before Kruskal, we need to understand how union find works. https://techblog-history-younghunjo1.tistory.com/257 is a good reference.

Kruskal

https://techblog-history-younghunjo1.tistory.com/262

This algorithm works on the principle that if parent of a is not equal to parent of b, then it does not form a cycle. Firstly we sort the graph based on cost so that we visit lowest cost edges first. Then, if that parent condition is met, we union parent those 2 and add the cost of that edge to our total cost.

Practice question

섬 연결하기

https://school.programmers.co.kr/learn/courses/30/lessons/42861

Easy applying template to this question

def find_parent(parent,x):
  if parent[x]!=x:
    parent[x]=find_parent(parent,parent[x])
  return parent[x]
  
def union(parent,a,b):
  a = find_parent(parent,a)
  b= find_parent(parent,b)
  if a<b:
    parent[b]=a
  else:
    parent[a]=b
    
def solution(n, costs):
  parent = [i for i in range(n+1)]
  # print(parent)  

  costs.sort(key=lambda x:x[2])
  # print(costs)
  total_cost=0
  for start,end,cost in costs:
    
    if find_parent(parent,start)!=find_parent(parent,end):
      union(parent,start,end)
      # print(start,end,cost)
      total_cost += cost
  # print(total_cost)
  return total_cost