[Code Tree] 그래프 알고리즘 - 크루스칼(Kruskal)

MST(Minimum Spanning Tree)

: 가중치가 있을 때, 최소한의 비용을 사용한 Spanning Tree 

 

✓ 최소한의 간선을 사용하여 그래프 내 모든 정점을 이어준다면, 그것을 Spanning Tree라고 부른다. 

- N개의 정점에 N-1개의 간선이 존재하는 그래프는 트리이다. (사이클이 없으며, 모든 노드들이 다 연결되어 있다. )

 

- 같은 그래프에서도 최소 스패닝 트리는 여러 개가 나올 수 있다. 

- 스패닝 트리 중 그 비용이 최대인 것을 최대 스패닝 트리라고 정의할 수 있다. 

- 스패닝 트리 또한 노드와 간선으로 이루어진 그래프이다. 

 

Union-Find

- 주로 서로소 집합을 관리하는 데 사용된다.

- 집합의 합치기(Union)와 대표 원소 찾기(Find) 연산을 효율적으로 수행하는 데 사용 

- 그래프 알고리즘에서 특히 최소 신장 트리(MST)나 연결 요소(Component)를 찾는 데 자주 사용

 

✓ 여러 개의 원소가 있고, 여러 개의 집합이 있을 때 ! 

- 특정 원소가 어떤 집합에 속해있는지 확인하고, 특정 집합을 합쳐야 할 일이 있을 때 사용하면 좋다. 

 

 

[동작 원리]

1. 초기화: 모든 원소는 각각 하나의 집합을 이루며, 자기 자신이 집합의 루트이다. 
2. Find 연산: 원소가 속한 집합의 루트를 찾는 연산 (일반적으로 트리 구조로 연결되어 있을 수 있기 때문에 경로 압축 기법을 사용해서 트리의 깊이를 최소화한다. )
3. Union 연산: 두 집합을 합칠 때는 Rank(깊이), Size(크기) 기반으로 합치기 기법을 사용 (작은 집합을 큰 집합으로 병합하는 방식)

 

[최적화 기법]

1. 경로 압축(Path Compression): Find 연산을 할 때, 경로 상의 모든 노드를 루트 노드로 직접 연결하여 트리의 깊이를 줄이는 방법
2. 랭크 기반 합치기(Union by Rank): 두 트리를 합칠 때, 트리의 높이가 더 작은 쪽을 큰 쪽에 합쳐서 트리의 높이를 최소화하는 방법 

 

[시간 복잡도]

• O(a(n))
  • a(n): 매우 느리게 증가하는 함수(아커만 함수의 역함수)

 

[동작 과정]

- 모든 노드가 연결되어 있지 않은 상황에서 시작

- uf 배열의 초기값은 자기자신 (uf는 그룹 번호를 의미)

[Code Tree] Novice High 그래프 알고리즘

 

- union() 연산을 사용해서 노드를 연결해준다. 

- union(1, 3) → uf[1] = 3 / union(5, 6) → uf[5] = 6

[Code Tree] Novice High 그래프 알고리즘

 

✓ uf 배열의 값은 그룹으로서의 의미 뿐만 아니라 실제 노드가 현재 가리키고 있는 부모 노드의 번호가 된다. 

- find(5) = 6 (X) / find(1) = 3 (Y) 이다. 이때 union(5, 1) 을 진행하면, uf[X] = Y 에 넣어준다. 

 

# Union-Find 자료구조
class UnionFind:
    def __init__(self, n):
        # 부모 노드를 자기 자신으로 초기화
        self.parent = [i for i in range(n)]

    # find 함수: 경로 압축을 통해 대표자를 찾음
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 경로 압축
        return self.parent[x]

    # union 함수: 두 집합을 합침
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.parent[rootX] = rootY  # x의 루트를 y의 루트에 연결
            
       '''     
        if rootX != rootY:
            # 랭크에 따라 트리의 높이를 최소화하며 합치기
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1
       '''

---

Kruskal Algorithm

: 가중치가 작은 간선부터 고른다. 

- 같은 가중치를 갖는 간선이 여러 개인 경우 아무 간선이나 고른다.

 

✓ 가중치가 작은 간선을 고르다가 사이클이 발생하면? 

→ 특정 간선을 선택하면, 두 노드에 union 연산을 수행해서 같은 집합으로 만들어준다. 

→ 만약 사이클이 발생한다면, 이미 두 노드는 같은 집합에 속한 상태이므로 미리 체크하여 합치지 않고 넘어간다. 

 

 

[시간 복잡도]

• O(ElogE)
  • 그래프 내 간선의 수가 E일 때, 간선을 정렬(O(ElogE)), 각 간선에 대해 union-find(O(logN))이므로, ElogE + ElogN

# Kruskal 알고리즘 구현
def kruskal(vertices, edges):  # 정점, 간선
    # 결과로 만들어질 MST 배열
    mst = []
    
    # 간선을 가중치에 따라 오름차순으로 정렬
    edges.sort(key=lambda edge: edge[2])  # (u, v, weight)에서 weight로 정렬
    
    # Union-Find 자료구조 초기화
    uf = UnionFind(len(vertices))

    # 간선을 하나씩 살펴봄
    for u, v, weight in edges:
        # u와 v가 다른 집합에 있을 때만 선택
        if uf.find(u) != uf.find(v):
            mst.append((u, v, weight))  # MST에 간선 추가
            uf.union(u, v)              # u와 v를 같은 집합으로 합침

    return mst