크루스칼(Kruskal) 알고리즘 1, 최소비용신장트리 / Union-Find 원리

---

1. 크루스칼(Kruskal) 알고리즘 이란?

크루스칼 알고리즘은 최소 비용으로 모든 노드를 연결하는 알고리즘 입니다. 흔히 여러 도시가 있을때 각 도시를 최소 비용으로 연결 하는 문제에서 쓰입니다.

​

​

2. 최소 비용 신장 트리(Minimum Spanning Tree)

위와 같은 그래프가 있을때, 6을 '노드' 또는 '정점' 이라고 부릅니다. 또한 25를 '비용' 또는 '엣지' 또는 '가중치' 라고 합니다. 크루스칼(Kruskal) 알고리즘으로 가능한 최소 비용으로 모든 노드를 연결하고 나면 최소 비용 신장 트리(Minimum Spanning Tree)가 만들어집니다. 가능한 최소 비용으로 모든 노드를 연결 하기 위해서는 비용이 가장 적은 엣지 부터 하나씩 연결 합니다. 하지만 트리는 여러 노드가 한 노드를 가리킬수 없습니다. 하나의 노드가 하나의 노드만 가리켜야 합니다. 만약 여러 노드가 한 노드를 가리키면 이를 '싸이클'(cycle) 또는 '회로' 가 생긴 다고 표현 합니다. 그럼 노드들의 엣지를 비용이 적은 순서대로 연결 하는 순서를 보겠습니다.

​

​

3. 그래프를 집합으로 표시 하기

처음에 각 노드들은 연결된 엣지들이 없으므로 각 노드들은 자기 자신만을 포함 하고 있는 부분 집합 입니다. 그리고 엣지 비용이 적은 순서대로 하나씩 엣지들을 연결 합니다. 엣지가 연결될 때 마다 노드들은 같은 집합에 속하게 됩니다. 그리고 모든 노드들이 같은 집합에 속하면 모든 노드가 연결이 다 되었으므로 '최소신장트리' 를 찾았으므로 끝이 납니다.

 

​

4. 사이클 Check

3번에서 그래프를 집합으로 표현해 보니, 사이클이 형성될 경우는 같은 집합 안에 속하게 되어 이 엣지가 사이클을 형성되는지 안되는지 체크 할 수 있습니다. 그럼 같은 집합 안에 속하는지 안속하는지는 어떻게 판단 할수 있을까요? 각 노드들을 '상향식 트리'로 생각 하는 것 입니다. 그래서 자기의 '최상위 노드' 만 기억을 하는 것 입니다. 그래서 '최상위 노드'가 같으면 같은 집합에 속해 있고, '최상위 노드'가 다르면 다른 집합에 포함되어 있다고 판단 하는 것 입니다. 아래 그림과 같이 배열 하나를 만들고 인덱스는 '노드', 값은 '최상위 노드' 로 취급하는 것 입니다. 여기서 '최상위 노드'를 찾는 방법을 'Find', 그리고 '최상위 노드' 를 비교하고 더 작은 값으로 치환하여 두 노드의 '최상위 노드'가 같아지므로써 엣지가 연결되었다고 판단할 수 있습니다. 이것을 'Union' 이라고 하며, 이 작업을 합쳐서 'Union-Find' 알고리즘 이라고도 합니다.

​

​

5. Union-Find

5-1. Union

한 트리를 다른 트리의 자식 노드로 만드는 작업

​

​

5-1-1. Union 함수 sudo 코드

union(u, v){
   x = find(u);
   y = find(v);
   parent[x] = y;
}

​​

​

5-2. Find

자신이 속한 트리의 루트를 찾는 작업

​

​

5-2-1. Find 함수 sudo 코드

find(x){
    if(x != parent[x])
        parent[x] = find(parent[x]);
    return parent[x];
}