크루스칼 알고리즘 편집하기

'''크루스칼 알고리즘'''(Kruskal's Algorithm)은 최소 신장 트리(MST, Minimum Spanning Tree)를 찾는 알고리즘 중 하나로, '''그리디 알고리즘'''(Greedy Algorithm)에 기반하여 동작한다. 그래프의 간선을 가중치가 작은 것부터 정렬한 후, '''서로소 집합(Disjoint Set)'''을 활용하여 최소 비용으로 모든 정점을 연결하는 방법을 찾는다.
==개요==
크루스칼 알고리즘은 간선 중심(edge-based)의 알고리즘으로, 그래프의 모든 간선을 정렬한 후, '''사이클을 형성하지 않는''' 간선을 하나씩 선택하여 최소 신장 트리를 구성한다.
==동작 과정==
*1. 그래프의 모든 간선을 '''가중치 기준으로 오름차순 정렬'''한다.
*2. 사이클을 형성하지 않는 간선을 '''가중치가 작은 것부터 선택'''한다.
*3. '''서로소 집합(Union-Find)'''을 사용하여 두 정점이 같은 집합에 속해 있는지 확인한다.
*4. 같은 집합이 아니라면 해당 간선을 '''MST에 추가'''하고, 두 정점을 하나의 집합으로 합친다.
*5. 모든 정점이 연결될 때까지 위 과정을 반복한다.
==예제==
다음 그래프를 예로 들어 크루스칼 알고리즘의 동작을 살펴보자.
  그래프 (정점: A, B, C, D, E, F, G)
  
  간선 리스트:  
  (A-B, 7), (A-D, 5), (B-C, 8), (B-D, 9), (B-E, 7),  
  (C-E, 5), (D-E, 15), (D-F, 6), (E-F, 8), (E-G, 9), (F-G, 11)
#간선을 가중치 기준으로 정렬:
#*(A-D, 5), (C-E, 5), (D-F, 6), (A-B, 7), (B-E, 7),
#*(B-C, 8), (E-F, 8), (B-D, 9), (E-G, 9), (F-G, 11), (D-E, 15)
#사이클을 만들지 않으면서 가중치가 작은 간선 선택:
#*선택된 간선: (A-D), (C-E), (D-F), (A-B), (B-E), (B-C), (E-G)
#최소 신장 트리(MST) 결과:
#*(A-D, 5), (C-E, 5), (D-F, 6), (A-B, 7), (B-E, 7), (B-C, 8), (E-G, 9)
==코드 예제==
<syntaxhighlight lang="python">
class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

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

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)

        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1

def kruskal(n, edges):
    edges.sort(key=lambda x: x[2])  # 간선을 가중치 기준으로 정렬
    ds = DisjointSet(n)
    mst = []
    
    for u, v, weight in edges:
        if ds.find(u) != ds.find(v):
            ds.union(u, v)
            mst.append((u, v, weight))

    return mst

# 예제 그래프 (정점 0~6)
edges = [
    (0, 1, 7), (0, 3, 5), (1, 2, 8), (1, 3, 9), (1, 4, 7),
    (2, 4, 5), (3, 4, 15), (3, 5, 6), (4, 5, 8), (4, 6, 9), (5, 6, 11)
]

mst = kruskal(7, edges)
print(mst)
</syntaxhighlight>
 출력 결과 예시:
 [(0, 3, 5), (2, 4, 5), (3, 5, 6), (0, 1, 7), (1, 4, 7), (4, 6, 9)]
==시간 복잡도==
크루스칼 알고리즘의 시간 복잡도는 다음과 같다.
*간선 정렬: O(E log E)
*서로소 집합 연산(Find, Union): O(α(V)) (거의 상수 시간)
*최종적으로 O(E log E)로 동작
==응용==
크루스칼 알고리즘은 여러 분야에서 활용된다.
*'''네트워크 설계''' → 최소 비용으로 네트워크 구축
*'''전력망 설계''' → 최소 전선 길이로 모든 도시 연결
*'''이미지 클러스터링''' → 그래프 기반 클러스터링 기법
==같이 보기==
*[[최소 신장 트리]]
*[[프림 알고리즘]]
*[[서로소 집합]]
==참고 문헌==
*Kruskal, Joseph B. "On the shortest spanning subtree of a graph and the traveling salesman problem." Proceedings of the American Mathematical Society, 1956.
*Cormen, Thomas H., et al. "Introduction to Algorithms." MIT Press, 2009.
[[분류:알고리즘]]
[[분류:트리 이론]]
[[분류:그래프 이론]]