설명

크루스칼 알고리즘이란 방향성이 없는 그래프가 있을 때 최소비용의 신장트리를 만들어내는 알고리즘이다.
(여기서 신장트리란 하나의 그래프가 있을 때 모든 노드를 포함아며 사이클이 발생하지 않는 트리를 의미한다. )

크루스칼 알고리즘을 단순히 보면 이렇게 설명할 수있다.

1. 모든 간선들을 오름차순으로 정렬후 작은 간선들 부터 확인한다.
2. 확인할 때에는 이간선이 사이클을 발생시키지 않으면 신장트리에 포함시킨다.
3. 모든 간선들을 순회하며 확인한다.

이런식으로 최소 신장트리를 완성시킬 수 있다.

사이클 판별 방법

여기서 궁금증은 사이클은 어떻게 판별하느냐 인데
사이클을 판별하는 방식은 다음과 같다.

1.간선을 확인한다.
2.연결된 간선을 구성하는 노드 2개가 각각 같은 집합(루트노드)가 같다면
사이클이 형성되는 것이므로 사이클이 발생한것이고
3.루트노드가 같지 않다면 두 집합을 union해준다.

코드로 구현하자면 이렇다

#사이클 발생여부 확인 코드 파이썬
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
parent = [0] * (N+1)

def find_parent(parent, x):
  if(x != parent[x]):
    parent[x] = find_parent(parent, parent[x])
    return find_parent(parent, parent[x])
  return x

def union_parent(parent, a, b):
  a = find_parent(parent, a)
  b = find_parent(parent, b)
  if(a < b):
    parent[b] = a
  else:
    parent[a] = b

for i in range(1,N+1):
  parent[i] = i

#사이클 발생여부 확인
flag = False
for _ in range(M):
  a, b = map(int, input().split())
  if(find_parent(parent, a) == find_parent(parent,b)):
    flag = True
    break;
  else:
    union_parent(parent, a, b)


if(flag == True):
  print('사이클이 발생했습니다.')
else:
  print('사이클이 발생하지 않았습니다.')

결국 사이클을 판별할 수 있다면 최소 신장트리를 구해주는
크루스칼 알고리즘을 구현해 볼 수 있다!!!

코드

#크루스칼 알고리즘 코드
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
edges = []

def find_parent(parent, x):
  if(x != parent[x]):
    parent[x] = find_parent(parent, parent[x])
    return parent[x]
    
  return x
  
def union_parent(parent, a, b):
  a = find_parent(parent, a)
  b = find_parent(parent, b)

  if(a < b):
    parent[b] = a
  else:
    parent[a] = b

parent = [0] * (N+1)
for i in range(1, N+1):
  parent[i] = i

for _ in range(M):
  a, b, c = map(int, input().split())
  edges.append((c, a, b))

edges.sort()

#크루스칼 알고리즘 시작
result = 0
for edge in edges:
  cost, a, b = edge
  if(find_parent(parent, a) != find_parent(parent, b)):
    result += cost
    union_parent(parent, a, b)

print(result)

시간복잡도

여기서 가장 오래걸리는 연산은 간선들의 정렬을 할 때 걸리는 시간이다.
파이썬의 정렬알고리즘의 시간복잡도는 O(NlogN)이므로

크루스칼 알고리즘의 시간복잡도는 O(ElogE)가 된다!!!