크루스칼(Kruskal) - 최소 신장 트리(MST)

개념

신장 트리(Spanning Tree)

• 모든 정점을 포함하면서 사이클이 없는 그래프
• 특징
  • 원 그래프의 모든 정점을 포함
  • 간선(node) 수 = 정점 수 - 1
  • 노드 간 사이클을 형성하지 않음
  • 한 그래프 내에서 여러 개의 신장 트리를 가질 수 있음

최소 신장 트리(Minimum Spanning Tree)

 

• 간선(node) 가중치의 합이 가장 작은 신장 트리
• 간선(node) 가중치가 가장 낮은 간선부터 탐색하여 신장트리를 구성하는 방식
• 대표 알고리즘 : Kruskal 알고리즘, Prim 알고리즘
  • 차이점
    • Kruskal 알고리즘 : 간선(node)를 중심으로 하여 신장 트리를 구성
    • Prim 알고리즘 : 정점(spot)을 중심으로 하여 신장 트리를 구성

 

크루스칼(Kruskal) 알고리즘

• 가장 작은 가중치를 갖는 간선(node)부터 탐색하며 최소 신장 트리를 구성하는 알고리즘

이론

1. 신장 트리 배열 생성
2. 가장 작은 간선(node) 가중치 탐색
3. 신장 트리 배열에 가장 작은 간선(node) 가중치 포함 여부 확인
   • 포함하지 않는다면 포함
   • 포함하고 있다면 지나감
4. 2번으로 돌아감

단계별로 밟아보기

1. 신장 트리를 저장할 배열을 생성

신장 트리	트리 간선 가중치
	0

2. 신장 트리 간선(node) 중 가중치가 가장 작은 것 탐색

 

3. 신장 트리 내 간선이 존재하는 지 확인 후, 없다면 추가

신장 트리	트리 간선 가중치
1,3	1

 

4. 2번째로 작은 간선(node) 가중치 탐색

5. 신장 트리 내 간선이 존재하는 지 확인 후, 없다면 추가

신장 트리	트리 간선 가중치
1,3,4,5	3

 

6. 다음 최소 간선(node) 가중치 탐색

 

7. 신장 트리 내 간선이 존재하는 지 확인 후, 없다면 추가

신장 트리	트리 간선 가중치
1,2,3,4,5	6

 

8. 다음 최소 간선(node) 가중치 탐색

 

9. 신장 트리 내 간선이 존재하는 지 확인 후, 없다면 추가

신장 트리	트리 간선 가중치
1,2,3,4,5,6	12

 

10. 신장 트리가 모든 정점을 포함한다면 중단

 

구현

• Union-Find 를 이용하여 구현
• 간선 가중치가 주어졌을 때, 간선 가중치를 기준으로 오름차순 정렬(최소 가중치부터 탐색)
• 순환하는 지 판단 후(Union-Find) 순환하지 않는다면 간선(node)를 저장하며 진행

2024.01.07 - [Algorithm/개념] - [알고리즘] Union-Find

[알고리즘] Union-Find

 

코드

# 1922 네트워크 연결
import sys
input = sys.stdin.readline

# MST (Ksruskal Algorithm)
# root 찾는 알고리즘(parent 배열 이용)
def find(num:int) -> int:
    # 부모 노드가 나, 나 자신이 root 이면 멈춤
    if parent[num] == num:
        return num
    # parent 배열을 통해 상위 노드를 찾아서 저장
    parent[num] = find(parent[num])
    return parent[num]

# 두 spot을 이어줌
def union(num1:int, num2:int) -> None:
    # 두 root를 찾아서
    x = find(num1)
    y = find(num2)
    # 순환되지 않는다면 하나의 고리로 이어줌
    if x != y:
        parent[y] = x
    return


def kruskal():
    # Kruskal 알고리즘 == 최소 신장트리
    node = []      # 지나온 노드 저장용
    cost = 0       # 비용 저장
    for i in range(M):        
        c, a, b = network[i]        # 비용이 가장 적은 노드부터 가져옴
        if find(a) == find(b):      # 순환되면 패스
            continue
        node.append(i)              # 지나온 노드는 저장
        union(a, b)                 # 지나갈 수 있다 == 이어져있다
        cost += c                   # 비용 저장
        if len(node) == N-1:        # 모든 노드 다 탐색했으면 비용 return -> 최소 비용임
            return cost            
    return cost