MST(Minimum Spanning Tree, 최소 신장 트리): 크루스칼 알고리즘

저번에 간단하게 봤던 크루스칼 알고리즘에 대해 자세하게 공부해봤다.

class DisjointSet:
    """유니온 파인드(Disjoint Set) 자료구조 구현"""
    def __init__(self, n):
        self.parent = list(range(n))  # 각 노드의 부모를 자기 자신으로 초기화

    def find(self, x):
        """루트 노드를 찾는 함수 (경로 압축 적용)"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 경로 압축
        return self.parent[x]

    def union(self, a, b):
        """두 노드를 같은 집합으로 합치는 함수"""
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a != root_b:
            self.parent[root_b] = root_a  # 한 쪽을 다른 쪽의 부모로 설정


def kruskal(n, edges):
    """크루스칼 알고리즘으로 MST 구하기"""
    edges.sort(key=lambda x: x[2])  # 간선 리스트를 가중치 기준으로 정렬
    ds = DisjointSet(n)  # 유니온 파인드 자료구조 생성
    mst = []  # MST 간선 리스트

    for u, v, weight in edges:
        if ds.find(u) != ds.find(v):  # 사이클이 생기지 않도록 확인
            ds.union(u, v)  # 두 정점을 합침
            mst.append((u, v, weight))  # MST 추가

    return mst  # 최소 신장 트리 반환


edges = [(0, 1, 1), (1, 2, 3), (0, 2, 2)]  # 그래프 간선(u, v, weight)
print(kruskal(3, edges))  # [(0, 1, 1), (0, 2, 2)]

 

find와 union 함수는 유니온 파인드(Disjoint Set) 자료구조의 핵심이다.

 

💡find(x) 함수의 역할

-> x가 속한 집합의 루트 노드를 찾는 역할

• 서로소 집합을 트리 구조로 관리하는데, find(x)를 호출하면 x가 속한 트리의 루트 노드를 찾는다.
• 크루스칼 알고리즘에서는 사이클이 발생하는지 확인할 때 find 함수를 사용한다.

 

💡 union(a, b) 함수의 역할

-> 두 개의 집합을 하나로 합치는 역할

• find(a)와 find(b)를 이용해 각각의 루트 노드를 찾은 뒤, 하나의 집합으로 합쳐준다. (즉, 같은 부모를 가지도록 설정한다)
• 크루스칼 알고리즘에서는 사이클이 발생하지 않을 때만 union 함수를 호출한다.
• 결국 MST를 만들 때 두 노르를 연결하는 역할을 한다.

 

💡find 함수에서 '경로 압축'

-> 트리 높이를 줄여서 find 함수가 더 빠르게 동작하도록 하는 기법

• 기본적인 find(x) 함수는 부모를 따라 루트 노드를 찾음 -> O(N) 시간 복잡도가 걸릴 수 있음.
• 경로 압축을 적용하면, 한 번 찾은 루트 노드를 바로 저장하여 다음 호출 시 더 빠르게 접근할 수 있다!

경로 압축 없는 경우 (느림)

def find(x):
    if parent[x] != x:
        return find(parent[x])  # 재귀적으로 루트 찾기(경로 압축 X)

 

경로 압축 적용한 경우 (빠름)

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # 부모 노드를 루트로 직접 갱신
    return parent[x]

이렇게 하면 모든 노드가 한 번의 find 함수 호출 후 바로 루트 노드를 가리킴!

결과적으로 find 연산이 평균적으로 O(1)에 가까워진다.

 

경로 압축을 한 것과 안 한 것의 차이점에 대해 자세히 알아보자.

📍경로 압축을 안 했을 때	📍 경로 압축을 했을 때
find(4) 호출 -> parent[4] = 3 -> parent[3] = 2 -> parent[2] = 1 (총 3번 탐색)	find(4) 호출 -> 한 번의 탐색 후 parent[4]를 1로 직접 갱신 (다음 호출부터 O(1))

즉, 경로 압축을 하면 같은 연산을 여러 번 반복할 필요가 없어져서 더 빠르다!