[알고리즘/Python] 크루스컬(kruskal) 알고리즘

크루스컬 알고리즘이란 

 

* 신장 트리 : 하나의 그래프가 있을 때, 모든 노드를 탐색하면서 사이클은 존재하지 않는 트리 

** 최소 신장 트리 : 그래프 G에서 노드 v를 포함하는 E에 속하는 Edge를 사용하여 만든 트리(신장트리)에서 가중치의 합이 가장 작도록 하는 트, 즉 최소비용으로 만들 수 있는 신장 트리 

 

크루스컬 알고리즘을 배우는데 왜 갑자기 신장트리가 나오는가 .. 에 대한 의문이 있으셨을 것이다. 왜 나온고하니 .. 

최소 신장 트리를 찾는 대표적인 알고리즘이 바로 크루스컬알고리즘 ! 

 

그리디 알고리즘에 속하며 순환 시, 사이클이 만들어지지 않도록 가중치가 가장 적은 간선을 선택하며 업데이트 된다 ~ 

 

 

크루스컬 알고리즘 동작원리 

1. 간선 데이터를 비용에 따라 오름차순 정렬 

2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지에 대한 여부 확인 

   (1) 사이클 발생 시 → 최소 신장트리에 간선 포함 (X)

   (2) 사이클 발생 X시 → 최소 신장트리에 간선 포함 (O) 

3. 모든 간선에 대해 2번의 과정을 반복 

 

 

대표 문제 

1922번: 네트워크 연결

코드 ! 

def find_parent(parent,x):
    #루트노드를 찾을때까지 .. 
    if parent[x] != x:
        parent[x] = find_parent(parent,parent[x])
    return parent[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

n= int(input())
m = int(input())

parent = [0]*(n+1)

#모든 간선을 담을 리스트
edges = []
#최종 비용을 담을 변수
result = 0

#부모 테이블 상에서, 부모를 자기 자신으로 초기화
for i in range(1,n+1):
    parent[i] = i

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

edges.sort()

for edge in edges :
    cost, a ,b = edge
    if find_parent(parent,a) != find_parent(parent,b):
        union_parent(parent,a,b)
        result += cost
print(result)

---

[참고 및 출처]

https://deep-learning-study.tistory.com/592

https://freedeveloper.tistory.com/278?category=888096 

https://velog.io/@kimdukbae/%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%B9%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Kruskal-Algorithm