최소 신장 트리 크루스칼과 프림 알고리즘
최소 신장 트리: 크루스칼과 프림 알고리즘
최소 신장 트리(Minimum Spanning Tree, MST)는 주어진 가중치 그래프(Weighted Graph)에서, 모든 정점을 연결하면서 간선들의 가중치 합이 최소가 되는 트리입니다. 즉, 최소 비용으로 모든 지점을 연결하는 방법을 찾는 문제로, 네트워크 설계 등 다양한 분야에 응용됩니다. MST를 구하는 대표적인 알고리즘으로 크루스칼과 프림 알고리즘이 있습니다.
🌳 크루스칼 알고리즘 (Kruskal's Algorithm)
- 핵심 아이디어 (Greedy) : 간선 중심의 접근법. 가중치가 가장 작은 간선부터 차례대로 선택하되, 사이클을 형성하지 않는 간선만 선택하여 MST를 만들어갑니다.
- 핵심 자료구조 : Union-Find (Disjoint Set). 사이클 생성 여부를 효율적으로 확인하기 위해 사용됩니다. 각 정점들이 어떤 집합에 속해있는지 관리합니다.
- 동작 과정
1. 모든 간선을 가중치에 따라 오름차순으로 정렬합니다. 2. 가중치가 가장 작은 간선부터 순서대로 확인합니다. 3. 현재 간선이 연결하는 두 정점이 서로 다른 집합에 속해 있다면(즉, 이 간선을 추가해도 사이클이 생기지 않는다면), 이 간선을 MST에 추가하고 두 정점을 같은 집합으로 합칩니다(Union). 4. MST가 (V-1)개의 간선을 가질 때까지 2-3번 과정을 반복합니다.
- 시간 복잡도 : O(E log E) (간선 정렬 시간) 또는 O(E log V)
🌱 프림 알고리즘 (Prim's Algorithm)
- 핵심 아이디어 (Greedy) : 정점 중심의 접근법. 임의의 시작 정점에서부터 시작하여, 현재 트리에 연결된 간선 중 가장 가중치가 작은 것을 선택하여 트리를 점차 확장시켜 나갑니다.
- 핵심 자료구조 : 우선순위 큐 (Priority Queue). 현재 트리에 인접한 간선들 중, 가중치가 가장 작은 간선을 효율적으로 선택하기 위해 사용됩니다.
- 동작 과정
1. 임의의 시작 정점을 선택하여 트리에 포함시킵니다. 2. 시작 정점과 인접한 모든 간선을 우선순위 큐에 넣습니다. 3. 우선순위 큐에서 가중치가 가장 작은 간선을 꺼냅니다. 4. 꺼낸 간선이 연결하는 정점이 아직 트리에 포함되지 않았다면, 그 간선과 정점을 트리에 추가합니다. 5. 새로 추가된 정점과 인접한 모든 간선들을 우선순위 큐에 넣습니다. 6. MST가 (V-1)개의 간선을 가질 때까지 3-5번 과정을 반복합니다.
- 시간 복잡도 : O(E log V) (우선순위 큐 사용 시)
💡 개발자 핵심 Point
- 언제 무엇을 사용할까?
> * 크루스칼 : 그래프에 간선이 적은 '희소 그래프(Sparse Graph)'일 때 유리합니다. (간선 정렬이 주요 연산이므로) > * 프림 : 그래프에 간선이 많은 '밀집 그래프(Dense Graph)'일 때 유리합니다.
- 다익스트라 vs 프림 : 두 알고리즘은 우선순위 큐를 사용하고 동작 방식이 매우 유사해 보이지만, 목적이 다릅니다.
> * 다익스트라 : 시작점에서부터 각 정점까지의 '최단 거리'를 구합니다. (거리의 총합) > * 프림 : 모든 정점을 '최소 비용'으로 연결하는 간선들의 집합을 구합니다. (선택된 간선들의 가중치 합)
- 활용 사례 : 여러 도시를 최소 비용으로 연결하는 통신망/전력망 설계, 여러 지점을 잇는 도로망 설계 등 네트워크 디자인 문제에 널리 사용됩니다.
