[알고리즘] 최소 신장 트리(2) - Kruskal 알고리즘

👨🏻‍💻 지난 포스팅에서는 하나의 정점에서 시작해 점차 영역을 넓혀나가는 Prim 알고리즘에 대해 알아봤다.

이번에는 숲 전체를 조망하며 가장 효율적인 길부터 연결해나가는,

또 다른 탐욕(Greedy) 알고리즘인 크루스칼(Kruskal) 알고리즘에 대해 알아보자.

kruskal-ezgif.com-gif-to-webp-converter

Kruskal 알고리즘

Kruskal 알고리즘은 모든 정점이 각각 독립된 집합으로 시작하여, 가중치가 가장 낮은 간선부터 차례대로 확인하며 사이클을 만들지 않는 간선만을 선택해 MST를 구축하는 방식이다.

Prim이 한 마을을 계속 확장하는 방식이라면, Kruskal은 흩어져 있는 수많은 외딴집들을 가장 저렴한 길부터 연결해서 거대한 하나의 마을로 만들어나가는 방식과 같다.

Kruskal 알고리즘 단계별 전략

모든 간선을 가중치 기준으로 오름차순 정렬
정렬된 순서대로 간선을 하나씩 확인하며, 현재 간선이 사이클을 형성하는지 검사
만약 사이클을 형성하지 않는다면, 해당 간선을 MST에 추가
MST가 V-1개의 간선을 가질 때까지 2~3번 과정을 반복

여기서 가장 중요한 질문이 나오게 된다.

🤨 "간선을 추가했을 때 사이클이 생기는지 어떻게 알 수 있을까?"

이 질문에 대한 가장 빠르고 효율적인 답이 바로 Union-Find 자료구조이다!

Union-Find: 최고의 관계 확인 & 팀 맺기 전문가

Union-Find는 서로소 집합(Disjoint Set)을 관리하기 위한 자료구조이다.

여기서 서로소 집합이란, 공통 원소가 없는 집합들을 의미한다.

Kruskal 알고리즘에서는 이 자료구조를 이용해 "두 정점이 이미 같은 집합(연결 요소)에 속해 있는가?"를 순식간에 판단하여 사이클 생성 여부를 확인한다.

Union-Find는 이름처럼 두 가지 핵심 연산을 가진다.

Find: 특정 원소가 속한 집합의 대표(Root)가 누구인지 찾아 알려줌
Union: 두 원소가 속한 집합을 하나로 합침

Union-Find의 초고속 비결: 최적화 기법

단순히 Find와 Union을 구현하면 트리가 한쪽으로만 길어지는 비효율적인 형태가 되어 성능이 저하될 수 있다. 이를 방지하기 위해 두 가지 강력한 최적화 기법이 사용된다.

경로 압축 (Path Compression)

"어차피 다 같은 대표님 모시는데, 중간 보고 라인 다 없애고 직통으로 연결하자!"

Find 연산을 수행하면서 거쳐 가는 모든 노드들을 전부 최종 대표(Root)의 직속 부하로 만들어버리는 기술이다.

이렇게 하면 다음번에 같은 노드를 찾을 땐 한 번에 대표를 찾을 수 있어 매우 빨라진다.
랭크 기반 합치기 (Union by Rank) 두 집합을 합칠(Union) 때, 더 작은 집합(낮은 트리)을 더 큰 집합(높은 트리)에 붙이는 전략이다. 이렇게 하면 전체적인 구조가 최대한 납작하게 유지되어 Find 연산의 효율이 보장된다.

이 두 가지 최적화 기법 덕분에 Union-Find의 각 연산은 거의 상수 시간(O(α(N)))에 가까운 엄청난 속도를 자랑하게 된다!

Kruskal 알고리즘 구현 (feat. Union-Find)

자 이제 Kruskal 알고리즘을 실제로 코드로 구현해자.

1. Union-Find 클래스 구현

# Union-Find 클래스: "우리 같은 팀이야?"를 알려주는 전문가
# 서로소 집합(Disjoint Set)을 관리하는 자료구조
# 서로소 집합: 서로 공통된 원소를 가지지 않는 두 집합 A, B를 서로소 관계라 함
# 크루스칼 알고리즘에서는 사이클이 생기는지 판별하는 데 결정적인 역할
class UnionFind:
    # 맨 처음, 모든 정점(노드)들이 각각 독립적인 팀이라고 선언해주는 생성자
    def __init__(self, n):
        # n: 총 정점의 개수
        # parent 리스트: 각 정점의 '부모'가 누군지 저장하는 리스트
        # 처음에는 모든 정점이 자기 자신을 부모로 가리킴 (자기 자신이 팀의 대표!)
        # [0, 1, 2, 3, 4, 5, 6] -> 1번의 부모는 1, 2번의 부모는 2...
        self.parent = list(range(n + 1))
        
        # rank 리스트: 트리의 '높이' 혹은 '깊이'를 기록
        # 두 팀을 합칠 때(Union), 이 랭크를 기준으로 더 효율적으로 합치기 위해 사용됨
        # 처음에는 모두 높이가 0인 납작한 상태
        self.rank = [0] * (n + 1)

    # find 연산: "그래서 우리 팀 대장이 누구야?" 특정 정점의 최종 보스(루트)를 찾는 함수
    def find(self, i):
        # i: 내가 속한 팀의 대표를 알고 싶은 정점 번호
        
        # 만약 나의 부모가 자기 자신이라면, 내가 바로 이 팀의 대표(루트)
        if self.parent[i] == i:
            return i
        
        # 아니라면, 나의 부모를 따라 계속 올라가 최종 대표를 찾음
        # ★경로 압축(Path Compression) 최적화★
        # 이 과정에서 만나는 모든 팀원들의 부모를 최종 대표로 바로 연결
        # "중간 관리자 다 없애! 이제부터 회장님께 직통 보고해!"
        # 이렇게 하면 다음번에 찾을 때 엄청나게 빨라짐
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    # union 연산: "오늘부터 두 팀은 한 팀이야!" 두 정점이 속한 팀을 하나로 합치는 함수
    def union(self, i, j):
        # i, j: 한 팀으로 묶고 싶은 두 정점 번호
        
        # 우선 각 정점의 최종 대표(루트)가 누군지 찾음
        root_i = self.find(i)
        root_j = self.find(j)

        # 두 대표가 다르다면, 아직 다른 팀이라는 의미
        if root_i != root_j:
            # ★랭크 기반 합치기(Union by Rank) 최적화★
            # 두 팀의 랭크(트리 높이)를 비교해서 더 낮은 트리를 높은 트리 밑에 붙임
            # 이렇게 해야 전체 트리가 너무 길쭉해지는 것을 막고, find 연산 속도를 유지 가능
            if self.rank[root_i] < self.rank[root_j]:
                self.parent[root_i] = root_j
            elif self.rank[root_i] > self.rank[root_j]:
                self.parent[root_j] = root_i
            else:
                # 만약 두 팀의 랭크가 같다면, 아무나 다른 쪽의 부모가 되고
                # 부모가 된 쪽의 랭크를 1 증가
                self.parent[root_j] = root_i
                self.rank[root_i] += 1
            return True  # 성공적으로 두 팀을 합쳤음을 알림
        
        # 만약 두 대표가 이미 같다면, 이들은 원래 같은 팀이라는 의미
        # 여기서 간선을 연결하면 사이클이 생기겠죠?
        return False # "이미 같은 팀이야!" 라고 알려줌 (사이클 발생 신호)

2. Kruskal 알고리즘 로직 구현

# 크루스칼 알고리즘 함수
def kruskal(n, edges):
    # 1. 간선 리스트를 가중치 기준으로 오름차순 정렬
    edges.sort(key=lambda edge: edge[2])
    
    # 2. Union-Find 자료구조를 n개의 정점으로 초기화
    uf = UnionFind(n)
    
    # 3. MST 결과를 저장할 리스트와 총 가중치를 초기화
    mst = []
    total_weight = 0
    
    # 4. 정렬된 간선 리스트를 하나씩 순회
    for u, v, weight in edges:
        
        # 5. union 연산을 이용해 두 정점을 합치고, 사이클 여부를 확인
        if uf.union(u, v):
            # uf.union()이 True를 반환 -> 사이클이 생기지 않음!
            # 이 간선은 MST의 일부! 결과 리스트에 추가!
            mst.append((u, v, weight))
            total_weight += weight
            
            # MST는 V-1개의 간선을 가지므로, 다 찾았다면 종료
            if len(mst) == n - 1:
                break
                
    return mst, total_weight

Kruskal 알고리즘 성능 분석: 시간 복잡도 ⏱️

Kruskal 알고리즘의 성능은 대부분 간선을 정렬하는 데 달려있다.

간선 정렬: 간선의 개수가 E일 때, 정렬에 효율적인 정렬 알고리즘(병합/퀵 정렬 등)을 사용하면 O(E log E) 시간이 걸린다.
Union-Find 연산: 최적화된 Union-Find 연산은 거의 상수 시간이므로, 모든 간선에 대해 연산을 수행해도 O(E * α(V))로 매우 빠르다.

따라서 전체 시간 복잡도는 더 오래 걸리는 간선 정렬 시간이 지배하므로, Kruskal 알고리즘의 시간 복잡도는 O(E log E) 이다.

Prim vs Kruskal 시간 복잡도 비교 분석 ⚔️

자, 이제 두 알고리즘의 표준 시간 복잡도를 비교하며 어떤 상황에서 어떤 알고리즘이 더 유리한지 자세히 살펴보자.

1. 표준 구현 방식의 시간 복잡도

먼저, 가장 일반적으로 사용되는 구현 방식의 시간 복잡도를 비교해 보자.

Prim 알고리즘 (우선순위 큐 사용): O(E log V)
Kruskal 알고리즘 (간선 정렬 + Union-Find 사용): O(E log E)

언뜻 보면 log V와 log E가 달라 보이지만, 사실상 두 복잡도는 같다고 볼 수 있다.

💡 O(E log E) vs O(E log V) : 사실상 같은 이유 빅오 표기법에서 로그의 밑은 상수로 취급되어 무시된다.

그래프에서 간선의 최대 개수는 $V(V-1)/2$ 이므로 E는 $O(V^2)$ 이다. 따라서 $logE$ 는 $logV^2$ , 즉 $2*logV$ 가 되어 $O(logV)$ 와 같다.

결국 Kruskal의 시간 복잡도도 $O(ElogV)$ 로 표현할 수 있어, 두 알고리즘의 표준 시간 복잡도는 동일하다고 볼 수 있다.

하지만 이것이 끝이 아니다. 진짜 비교는 이제부터 시작이다..!

바로 그래프의 밀도(Density)에 따라 유불리가 갈리기 때문이다.

2. 그래프 밀도에 따른 성능 비교

상황 1: 희소 그래프 (Sparse Graph) 🌳

정의: 간선의 개수(E)가 정점의 개수(V)에 비해 매우 적은 그래프. (예: E ≈ V)
분석:
- Prim: O(E log V) → O(V log V)
- Kruskal: O(E log E) → O(E log V) → O(V log V)
결론: 희소 그래프에서는 두 알고리즘의 성능이 거의 비슷하다.
하지만 Kruskal은 간선 정렬 후 바로 작업을 시작하는 반면, Prim은 우선순위 큐에 넣고 빼는 과정이 있어 실제 실행 시간(Running Time)은 Kruskal이 약간 더 빠른 경향을 보인다.
대부분의 코딩 테스트 문제나 현실의 도로망, 파이프라인 같은 경우는 희소 그래프에 해당

상황 2: 밀집 그래프 (Dense Graph) 🕸️

정의: 간선의 개수(E)가 정점 개수의 제곱(V^2)에 가까울 정도로 매우 많은 그래프 (모든 정점 쌍이 거의 다 연결된 상태)
분석:
- Prim (우선순위 큐 사용): E가 O(V^2) 이므로, O(E log V) → O(V^2 log V)
- Kruskal: E가 O(V^2) 이므로, O(E log E) → O(V^2 log V^2) → O(V^2 log V)
결론: 이 경우에도 두 알고리즘의 빅오 표기법은 동일

하지만 여기서 Prim 알고리즘의 다른 구현 방식이 빛을 발한다.

Prim (배열/리스트 사용): O(V^2)
- 우선순위 큐 대신 단순 배열을 사용해 매번 MST에 포함되지 않은 정점들 중 가장 distance가 짧은 것을 찾는 방식
- O(V^2)의 복잡도는 O(V^2 log V) 보다 명백히 빠름

따라서 밀집 그래프에서는 우선순위 큐를 사용하지 않은 배열 기반 Prim 알고리즘이 O(V^2)으로 가장 효율적

🤨 그래서 뭘 써야 할까?

그래프 종류	상황 (E vs V)	Prim(p-queue) `O(E log V)`	Kruskal `O(E log E)`	최적 알고리즘
희소 그래프	`E ≈ V`	`O(V log V)`	`O(V log V)`	Kruskal (실행 시간 우세)
밀집 그래프	`E ≈ V^2`	`O(V^2 log V)`	`O(V^2 log V)`	Prim (배열) `O(V^2)`
일반적인 경우	대부분의 상황	`O(E log V)`	`O(E log V)`	Kruskal (구현이 간편)

마치며

Prim이 하나의 컴포넌트를 점진적으로 키워나갔다면,

Kruskal은 숲 전체의 간선들을 탐욕적으로 선택하여 여러 컴포넌트들을 하나로 합쳐나갔다.

이로써 최소 신장 트리를 만드는 두 가지 대표적인 방법을 모두 알아보았다. 🎉

참고 자료

snu open courseware: Introduction to Data Structures

https://www.w3schools.com/dsa/dsa_algo_mst_kruskal.php

https://hideoushumpbackfreak.com/algorithms/data-struct-union-find

Kruskal 알고리즘​

​Kruskal 알고리즘 단계별 전략​

​Union-Find: 최고의 관계 확인 & 팀 맺기 전문가​

​Union-Find의 초고속 비결: 최적화 기법​

​Kruskal 알고리즘 구현 (feat. Union-Find)​

​1. Union-Find 클래스 구현

2. Kruskal 알고리즘 로직 구현​

​Kruskal 알고리즘 성능 분석: 시간 복잡도 ⏱️​