그래프에서 최소 신장 트리(MST) : Kruskal과 Prim 알고리즘 비교

최소 신장 트리를 생성하는 두 가지 대표 알고리즘의 원리와 차이에 대해 살펴보겠습니다.

 

1️⃣ 최소 신장 트리(MST)란?

최소 신장 트리(Minimum Spanning Tree, MST)는 가중치가 있는 연결 그래프에서 모든 노드를 연결하되, 간선의 가중치 합이 최소가 되는 트리를 의미합니다.

MST는 네트워크 설계, 도로 건설, 전기 회로 설계와 같은 문제에서 활용됩니다. MST를 생성하는 대표적인 알고리즘으로는 Kruskal 알고리즘과 Prim 알고리즘이 있습니다.

 

2️⃣ Kruskal 알고리즘

Kruskal 알고리즘은 모든 간선을 가중치 순으로 정렬한 후, 최소 가중치 간선부터 순차적으로 선택하여 MST를 구축합니다. 사이클이 생성되지 않도록 간선을 추가하는 것이 핵심입니다.

✅ 구현 방법

# Python으로 Kruskal 알고리즘 구현
class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, node):
        if self.parent[node] != node:
            self.parent[node] = self.find(self.parent[node])
        return self.parent[node]

    def union(self, u, v):
        root1 = self.find(u)
        root2 = self.find(v)
        if root1 != root2:
            if self.rank[root1] > self.rank[root2]:
                self.parent[root2] = root1
            elif self.rank[root1] < self.rank[root2]:
                self.parent[root1] = root2
            else:
                self.parent[root2] = root1
                self.rank[root1] += 1

def kruskal(n, edges):
    ds = DisjointSet(n)
    edges.sort(key=lambda x: x[2])  # 간선 정렬
    mst = []
    for u, v, w in edges:
        if ds.find(u) != ds.find(v):
            ds.union(u, v)
            mst.append((u, v, w))
    return mst

edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
print(kruskal(4, edges)) # 출력: [(2, 3, 4), (0, 3, 5), (0, 1, 10)]
            

Kruskal 알고리즘은 주로 간선 중심 그래프에서 효율적입니다.

 

3️⃣ Prim 알고리즘

Prim 알고리즘은 임의의 노드에서 시작하여, 이미 선택된 노드 집합에서 최소 가중치 간선을 추가하여 MST를 확장합니다.

✅ 구현 방법

# Python으로 Prim 알고리즘 구현
import heapq

def prim(n, graph):
    visited = [False] * n
    min_heap = [(0, 0)]  # (가중치, 노드)
    mst = []
    while min_heap:
        weight, u = heapq.heappop(min_heap)
        if not visited[u]:
            visited[u] = True
            mst.append(weight)
            for v, w in graph[u]:
                if not visited[v]:
                    heapq.heappush(min_heap, (w, v))
    return sum(mst)

graph = {
    0: [(1, 10), (2, 6), (3, 5)],
    1: [(0, 10), (3, 15)],
    2: [(0, 6), (3, 4)],
    3: [(0, 5), (1, 15), (2, 4)]
}
print(prim(4, graph)) # 출력: 19
            

Prim 알고리즘은 노드 중심 그래프에서 효율적입니다.

 

4️⃣ Kruskal vs Prim : 차이점

특징	Kruskal 알고리즘	Prim 알고리즘
접근 방식	간선 중심	노드 중심
초기 단계	모든 간선을 정렬	임의의 노드에서 시작
적합한 그래프	간선이 적은 희소 그래프	간선이 많은 밀집 그래프
시간 복잡도	O(E log E)	O(E log V)

 

결론

Kruskal과 Prim 알고리즘은 각각의 강점을 가진 효율적인 MST 생성 방법입니다. Kruskal은 간선 중심 접근으로 간선이 적은 그래프에 적합하고, Prim은 노드 중심 접근으로 밀집 그래프에서 성능이 우수합니다.

개인적으로, 이 두 알고리즘은 단순한 문제 해결 방법을 넘어, 그래프의 구조에 따라 적합한 알고리즘을 선택하는 사고방식을 가르쳐준다고 생각합니다. 실제 문제에서 그래프의 특성과 요구 사항을 분석하고, 적절한 알고리즘을 적용하는 것이 중요합니다.

다양한 그래프 문제를 해결하며 Kruskal과 Prim 알고리즘의 차이와 활용법을 익혀보세요. 이를 통해 데이터 구조와 알고리즘 설계 능력을 한 단계 높일 수 있을 것입니다.

 

© 2024 favorites. All rights reserved.