Kruskal Algorithm(크루스칼 알고리즘)

크루스칼 알고리즘이란? 

최소 신장 트리를 구하기 위한 알고리즘이다. 크루스칼 알고리즘은 그리디 알고리즘의 일종이다. 즉, 그래프의 간선을 오름차순으로 정렬한 후, 최소 비용의 간선을 선택한다. 

 

최소 신장 트리

모든 정점을 포함하고 사이클이 없는 연결 선을 그렸을 때, 가중치의 합이 최소가 되는 그래프

 

Kruskal 알고리즘 동작

 

1. 그래프 간선들을 가중치의 오름차순으로 정렬한다. 
2. 정렬된 간선 리스트에서 사이클이 생성되지 않는 간선을 순서대로 선택한다.
    2.1. 가장 작은 가중치를 먼저 선택한다.
    2.2. 사이클을 형성하는 간선은 제외한다. 
3. 해당 간선을 현재의 MST(Minimum Spanning Tree 최소 신장 트리)에 추가한다. 

 

사이클 생성 여부를 확인하는 방법

추가하고자 하는 간선의 양끝 정점이 같은 집합에 속해 있는지 먼저 검사해야 한다. 검사를 위해서 'union-find' 알고리즘을 이용한다.

 

union-find 알고리즘

union-find란 Disjoint Set을 표현할 때 사용하는 알고리즘이다. 집합을 구현하는데 비트 벡터, 배열, 연결 리스트를 이용할 수 있으나 그 중 가장 효율적인 트리 구조를 이용하여 구현한다. 아래의 3가지 연산을 이용하여 Disjoint Set을 표한한다. 

make-set(x) 
x를 유일한 원소로 하는 새로운 집합을 만든다.
union(x,y) 
x가 속한 집합과 y가 속한 집합을 합친다. 
find(x) 
x가 속한 집합의 대표값(루트  노드 값)을 반환한다. 즉, x가 어떤 집합에 속해 있는지 찾는 연산이다.

 

예제

큰 수 만들기(프로그래머스) 

#전형적인 크루스칼 알고리즘 문제였다. 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 다시 말해 최소 신장 트리를 만들기 위한 알고리즘이다.
#find와 union을 통해 부모노드를 찾고 연결시킨다. 부모노드가 서로 같으면 사이클이 생성되므로 union하지 않는다. 

def solution(n, costs):
    answer = 0

    #parent set
    parent=[k for k in range(n)]
    print(parent)
    #costs sort
    costs.sort(key=lambda x: x[2])

    #find 메소드
    def find(v): 
        if parent[v]==v: 
            return v
        parent[v]=find(parent[v]) #경로 압축
        return parent[v]
      
            
    #union 메소드
    def union(v1,v2): 
        parent[find(v2)]=parent[find(v1)]

    for cost in costs:
        #부모가 같으면 사이클 생성을 의미하므로, 부모가 다르면 union해서 parent을 갱신한다(노드 간 연결을 의미한다).
        if find(cost[0])!= find(cost[1]): 
            union(cost[0], cost[1])
            answer+=cost[2]


    
    print(answer)
    return answer

solution(4,[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]])