[Graph] Kruskal’s algorithm (크루스칼 알고리즘)

크러스컬 알고리즘(Kruskal’s algorithm)은 최소 비용 신장 부분 트리(MST)를 찾는 알고리즘이다. 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 이 알고리즘은 O(ElogV) 의 시간복잡도를 가진다. 자세한 내용은 여기를 클릭! (출처 : 위키백과)

 

 

개요

크러스컬 알고리즘은 아래의 순서대로 작동한다.

1. 그래프의 각 꼭짓점이 각각 하나의 나무(자료구조의 tree)가 되도록 하는 숲 F 을 만든다.
2. 모든 변을 원소로 갖는 집합 S 를 만든다.
3. S가 비어있지 않는 동안
   1. 가장 작은 가중치의 변을 S 에서 하나 빼낸다.
   2. 그 변이 어떤 두 개의 나무를 연결한다면 두 나무를 연결하여 하나의 나무로 만든다.
   3. 그렇지 않다면 그 변은 버린다.

알고리즘이 종료됐을 때 숲 F는 하나의 최소 비용 신장 부분 그래프만을 가지게 된다.

 

상호 배타 집합 표현

✅ 서로소 집합 (Disjoint-sets)

• 서로소 또는 상호배타 집합들은 서로 중복 원소가 없는 집합들이다. 다시 말해 교집합이 없다.
• 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분하며, 이를 대표자(repersentative) 라 한다.
• 상호 배타 집합은 연결 리스트 또는 트리 등으로 표현한다.
• 상호배타 집합 연산
  • Make-Set(x)
  • Find-Set(x)
  • Union(x, y)

 

✅ 트리로 표현

• 하나의 서로소집합을 하나의 트리로 표현한다.
• 자식 노드가 부모노드를 가리키면 루트노드가 대표자가 된다.

 

Basic Code

① Make-Set(x)

유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산. 초기값을 설정하기 위함이며, 대부분은 경우 초기값으로 자기자신을 부모로 하여 생성한다.

def Make_Set(x):
        p[x] = x

 

② Find-Set(x)

x 를 포함하는 집합을 찾는 연산. 서로소 집합인 경우 대표자(repersentative) 를 찾을 때 사용한다. 재귀적으로 부모노드로 올라가다가, 부모노드가 자기자신인 노드 (서로소집합의 루트노드 이자, 대표자) 를 찾아 리턴한다.

def Find_Set(x):
        if x == p[x] : return x
        else: return Find_Set(p[x])

 

③ Union(x, y)

x와 y를 포함하는 두 집합을 통합하는 연산. Find-set()으로 각 노드의 루트 노드를 찾는다. 가장 상단의 루트노드를 찾으면, 루트 노드를 연결한다. 둘중 하나를 부모로 지정하여 서로소집합을 합치는 것이다.

def Union(x, y):
        p[Find_Set(y)] = Find_Set(x)

 

연산의 효율을 높이는 방법

• Rank를 이용한 Union
  • 각 노드는 자신을 루트로 하는 subtree의 높이를 랭크Pank 라는 이름으로 저장한다.
  • 두 집합을 합칠 때 rank가 낮은 집합을 rank가 높은 집합에 붙인다.
• Path compression
  • Find-set을 행하는 과정에서 만나는 모든 노드들이 직접 root를 가리키도록 포인터를 바꾸어준다.

Basic Code + Rank

① Make-Set(x)

def Make_Set(x):
        p[x] = x # 노드의 x의 부모 노드 저장
        rank[x] = 0 # 루트 노드가 x인 트리의 랭크 값 저장

 

② Find-Set(x)

특정 노드에서 루트까지의 경로를 찾아가면서 노드의 부모정보를 갱신한다.

def Find_Set(x):
        if x != p[x] : 
                p[x] = Find_Set(p[x])
        return p[x]

 

③ Union(x, y)

x와 y를 포함하는 두 집합을 통합하는 연산. Find-set()으로 각 노드의 루트 노드를 찾는다. 가장 상단의 루트노드를 찾으면, 루트 노드를 연결한다. 둘중 하나를 부모로 지정하여 서로소집합을 합치는 것이다.

def Union(x, y):
        Link(Find_Set(x), Find_Set(y))

def Link(x, y):
        if rank[x] > rank[y]: # rank : 트리의 높이
                p[y] = x
        else:
                p[x] = y
                if rank[x] == rank[y]:
                        rank += 1

연산의 효율을 높이는 방법

 

 

크리스컬 알고리즘은 최소신장트리를 만드는 방법이다. 그래프를 최소 비용으로 연결하는 한개의 루트를 구성하는 것이기 때문에, 경로를 순환하지 않게 만드는 것이 중요하다. 트리 구조로 루트에서 단일 가지로 뻗어나가는 것으로 표현하는것이 관건이다.

이를 위해 2가지 함수 구현이 필요하고, 이를 find & union 이라고 한다. find 함수는 정점의 루트 노드를 찾고, union 함수는 경로를 연결하는 역할을 한다. 경로를 연결하는 것은 두 정점의 루트 노드로 올라가서 두개의 루트를 더 작은 쪽으로 합친다. 순환하지 않는 트리 형태로 연결하는 것이다.

def solution(n, costs):
        # 함수 정의부 #
    def find(x): # 루트를 찾는 함수
        if x != parent[x]: # 내가 루트가 아니면
            parent[x] = find(parent[x]) # 부모노드로 올라가서 탐색을 다시
        return parent[x] # 루트 노드에 도달하면 루트를 리턴

    def union(a, b): # a, b 경로를 합치기 위함
        root_a = find(a) # 루트를 찾아서
        root_b = find(b)
        parent[root_b] = root_a # 루트를 연결

        # 실행부 #
    costs.sort(key = lambda x : (x[2])) # 가중치 오름차순 정렬
    parent = [me for me in range(n)] # 정점의 부모노드를 저장 (초기값 자기자신)
    result = 0 # 최소비용
    node = 0 # 연결한 간선 수

    for v, w, d in costs:
        if find(v) != find(w): # 루트가 다르면, 사이클 아님
            union(v, w) # 연결
            result += d
            node += 1
        if node == n - 1: # 모든 정점을 연결하는 최소 간선수
            break
    return result

print(solution(4, [[0,1,1],[0,3,2],[1,2,3],[1,3,2],[2,3,4]]))