[최소신장트리] 크루스칼 알고리즘

신장 트리(Spanning Tree)

- 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 그래프

 

신장 트리의 특징

1. 모든 노드를 포함

2. 사이클이 없음

3. 연결성 유지 : 그래프의 모든 노드를 연결

---

최소 신장 트리 (MST, Minimum Spanning Tree)

- 신장 트리에서 가중치의 합이 최소가 되는 신장 트리

- 알고리즘 종류 : 프림 알고리즘, 크루스칼 알고리즘

 

 

프림 알고리즘(Prim's Alogrithm)

- 시작 노드를 선택한다.

- 해당 노드와 가장 작은 가중치의 간선을 선택한다.

- 새로운 노드를 트리에 추가한다.

- 선택한 노드의 집합을 확장하면서 최소 신장 트리를 형성한다.

 

- 간선의 수가 적을 때 적합하다.

- Priority Queue 우선순위 큐 사용

- 시간 복잡도 : O(E log E) // E는 간선의 수

 

 

크루스칼 알고리즘(Kruskal's Alogrithm)

- 그래프의 간선을 가중치의 오름차순으로 정렬하고, 가장 작은 가중치부터 선택해서 최소 신장 트리를 구성한다.

- 사이클을 형성하지 않는 간선을 선택하면서 트리를 확장한다.

- 유니온 파인드(Union Find) 자료구조 사용으로, 사이클 여부 확인

 

- 그리디 알고리즘 사용

- 간선의 수가 많을 때 적합하다.

- 시간 복잡도 : O(E log V) // V는 노드의 수

---

[최소 신장 트리 알고리즘 예제]

백준 1414번

https://www.acmicpc.net/problem/1414

1414번: 불우이웃돕기

- N 개의 컴퓨터가 서로 연결되어 있는 랜선 길이가 주어질 때

- 모든 컴퓨터가 서로 연결되도록 만들고, 랜선 길이가 최대 값이 되는 값을 출력

 

 

- 파이썬 코드

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


def union(parent, a, b):  # 두 원소가 속한 집합 합치기
    a = find(parent, a)
    b = find(parent, b)
    if a < b:  # 더 작은 번호가 부모 노드
        parent[b] = a
    else:
        parent[a] = b


n = int(input())  # 컴퓨터 개수
edges = []
result = 0
parent = [i for i in range(n + 1)]  # 부모 테이블 초기화

for i in range(n):
    s = input()

    for j in range(len(s)):
        cost = 0  # 0이면 그대로
        ch = s[j]
        if ch.islower():  # 소문자
            cost = ord(ch) - ord('a') + 1
        elif ch.isupper():
            cost = ord(ch) - ord('A') + 27
        edges.append((cost, i + 1, j + 1))
        result += cost  # 모든 비용 계산

edges.sort()  # cost 오름차순 정렬

for cost, a, b in edges:
    if cost == 0:
        continue
    if find(parent, a) != find(parent, b):  # 사이클 발생 하지 않는 경우에 MST 포함
        union(parent, a, b)
        # print(cost)
        result -= cost

flag = True
for i in range(1, n + 1):
    if find(parent, i) != 1:
        flag = False

if flag:
    print(result)
else:
    print(-1)

---

백준 10423번

https://www.acmicpc.net/problem/10423

10423번: 전기가 부족해

- 도시의 개수 N

- 설치 가능한 케이블 수 M

- 발전소 개수 K

- 모든 도시에 전기를 공급할 수 있도록 연결되어 있고, 케이블 설치 최소 비용 구하기

- 발전소가 설치된 도시는 연결하지 않아도 된다.

 

 

- 파이썬 코드

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


def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


n, m, k = map(int, input().split())  # 도시 개수, 케이블 수, 발전소 개수
numbers = list(map(int, input().split()))  # 발전소 설치된 도시 번호
parent = [i for i in range(n + 1)]
edges = []
answer = 0

for num in numbers:  # 발전소 설치된 도시의 루트를 0 으로 초기화
    parent[num] = 0

for _ in range(m):
    u, v, w = map(int, input().split())  # u 도시와 v 도시 연결 비용 w
    edges.append((w, u, v))

edges.sort()

for cost, a, b in edges:
    if find(parent, a) != find(parent, b):  # 사이클이 아닌 경우에만 계산
        union(parent, a, b)
        answer += cost

print(answer)