[AIGORITHM THEORY] KRUSKAL (크루스칼) - MST 개념정리

개념

MST (최소 비용 신장 트리)

• 무방향 가중치 그래프에서 최저의 비용을 갖는 신장 트리
  • 간선들의 가중치 합이 최소인 신장 트리를 의미한다.
• 최소 비용 신장 트리를 만드는 알고리즘
  1. KRUSKAL
  2. PRIM
• 신장 트리를 만드는 제한 조건
  • 그래프 내에 있는 간선들만 사용해야한다.
  • 총 n-1개의 간선만을 사용해야 한다.
  • 사이클을 생성하는 간선은 사용이 금지된다.

원리

1. 그래프 G의 모든 간선을 가중치에 따라 오름차순으로 정리한다.
2. 그래프 G에 가중치가 가장 낮은 간선을 삽입한다.
   • 사이클을 형성하는 간섭 불가능 → 다음으로 가중치가 낮은 간선 삽입
3. 그래프 G에 간선이 n-1개가 삽이될때까지 2. 과정을 반복한다.

• 크루스칼 알고리즘을 활용해 만들어넨 최소 비용 신장 트리

알고리즘

• 아래에 적힌 코드를 직접 해석하는게 쉽다.
• 그림을 통해 이해하는 과정이 빠르기에, 내가 학습을 하며 참고한 여러 링크를 참고해 이해하는편이 좋다. 기본적인 내용은 필기항목에 적어두었다.

---

필기

• 크루스칼 알고리즘은 그리디 알고리즘의 일종이다. 그래프의 간선들을 가중치의 오름차순으로 정렬해 놓은뒤, 사이클을 형성하지 않는 선에서 정렬된 순서대로 간선을 선택한다.

• 사이클 판단하기 - Union & Find 활용

  • Union-Find : Disjoint Set (서로소 집합) 을 표현하는 자료구조

    # 특정 원소가 속한 집합 찾기
    def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
        if parent[x] != x:
            parent[x] = find_parent(parent, parent[x])
        return parent[x]
    
    # 두 원소가 속한 집합을 합치기
    def union_parent(parent, u, v):
        u = find_parent(parent, u)
        v = find_parent(parent, v)
        if u < v:
            parent[v] = u
        else:
            parent[u] = v

예제 문제!

• 백준 - 1922 / 네트워크 연결 https://www.acmicpc.net/problem/1922
  

---

코드

# 특정 원소가 속한 집합 찾기
def find_parent(parent, x):
# 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, u, v):
    u = find_parent(parent, u)
    v = find_parent(parent, v)
    if u < v:
        parent[v] = u
    else:
        parent[u] = v

# 노드 개수와 간선 개수 입력받기
v, e = map(int, input().split())
parent = list(range(v+1)) # 부모 테이블에서 부모를 자기 자신으로 초기화
edges = [] # 모든 간선을 담을 리스트
result = 0 # 최종 비용을 담을 변수
# 모든 간선에 대한 정보 입력

for _ in range(e):
    u, v, cost = map(int, input().split())
    edges.append((cost, u, v))

edges.sort() # 간선을 비용순으로 정렬

for edge in edges: # 간선을 하나씩 확인
    cost, u, v = edge
    # 사이클이 발생하지 않는 경우에만 집합에 포함
    if find_parent(parent, u) != find_parent(parent, v):
        union_parent(parent, u, v)
        result += cost
        
print(result)

---

참고자료

• 감사하신 홍정희 교수님의 강의자료
• https://chanhuiseok.github.io/posts/algo-33/
• https://withhamit.tistory.com/322