우주의 IT 소행성

신장 트리, 스패닝 트리 (Spanning Tree)

- N개의 정점으로 이루어진 무방향 그래프에서 N개의 모든 정점과 N - 1개의 간선으로 만들어진 트리

최소 비용 신장 트리 (Minimum Cost Spanning Tree)

- 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리

- 여기서 의미하는 가중치란 비용, 거리, 시간 등을 의미한다.

크루스칼 알고리즘 (Kruskal Algorithm)

- 최소 비용 신장 트리를 구할 수 있는 효과적인 알고리즘

- 가중치가 높은 간선을 제거하면서 최소 비용 신장 트리를 만드는 방법

- 탐욕적인 (Greedy한) 방법임 

크루스칼 알고리즘의 동작 방식 - 1 (가중치가 높은 간선을 제거하는 방식)

1. 그래프의 모든 간선을 가중치에 따라 내림차순으로 정렬

2. 그래프에서 가중치가 가장 높은 간선을 제거 (이 때, 정점을 그래프에서 분리시키는 간선은 제거할 수 없음)

-> 즉 간선을 제거했을 떄 더이상 그래프가 이어지지 않고 끊어지면 안된다는 말

3. 그래프의 간선이 N - 1개 남을 때 까지 2를 반복

크루스칼 알고리즘의 동작 방식 - 2 (가중치가 낮은 간선을 삽입하면서 만드는 방식)

1. 그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬

2. 그래프의 가중치가 제일 낮은 간선을 삽입 (이 때, 사이클을 형성하는 간선은 삽입할 수 없음)

-> 즉, 간선을 놓았을 때 그래프가 사이클을 이루게 되면 안 된다는 말

3. 그래프의 간선이 N - 1개 남을 때 까지 2를 반복

그렇다면, 이 그래프가 사이클을 이루고 있는지는 어떻게 알아?

-> 유니온 파인드(Union-find) 알고리즘을 이용해 확인 할 수 있다.

Kruskal 알고리즘의 시간 복잡도는?

- 간선들을 정렬하는 초기 시간에 좌우

- 간선 e개를 효율적으로 정렬한다면 O(eloe2e)로 해결 가능

참고한 글 (자세한 설명)

https://blog.naver.com/diddnjs02/222000205465