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

크루스칼 알고리즘을 공부하기 전에, 스패닝 트리에 대해서 먼저 알아야 한다.

span 은 '완전히 덮다' 라는 느낌의 뜻을 가지고 있는 단어이고, 트리는 사이클이 없는 그래프이다.

그래서 스패닝 트리는 그래프의 모든 노드를 포함하는 트리이다. 위의 경우에도 스패닝 트리이고, 밑의 경우에도 스패닝 트리이다.

하나의 그래프에서 스패닝트리는 여러개 존재할 수 있다.

스패닝 트리의 가중치를 합하면 weight를 알 수 있는데, 그래프에서 weight의 값이 최소인 스패닝 트리를

최소 스패닝 트리 (Minimum Spanning Tree) 이라고 한다. 위의 그래프에서 표시된 트리가 최소 스패닝 트리이다.

---

크루스칼 알고리즘을 알기 위해서 또 알아야할 개념중에 하나가 Cut Property 라는 것이다.

T1과 T2는 서로 다른 독립된 트리이다. 이제 두개의 그래프 합치기 위해 사이에 간선을 그어 최소 스패닝 트리를 만들어야 한다.

어떻게 간선을 그어야 할까 ?

위의 연결된 간선의 가중치를 임의로 적어보았다. 이 중에서 하나의 간선을 그어 최소 스패닝 트리를 얻으려면

가중치가 1인 가장 작은 간선을 그어야 최소 스패닝 트리에 포함되는 간선이 된다.

왜냐하면 최소 스패닝 트리의 정의를 생각해보면 답이 쉽게 나오는데, weight가 가장 작은 트리이기 때문이다.

---

이제 크루스칼 알고리즘에 동작 원리에 대해서 알아보자. 의외로 알고리즘 자체는 간단하다.

처음에 주어진 그래프의 각 노드를 하나의 독립된 최소 스패닝 트리라고 보고 시작한다.

그리고 가중치가 가장 작은 간선부터 이어 본다. 위의 경우 1을 계속 연결하다 보면

5 와 7 을 이을 때 싸이클이 생기기 때문에 연결하면 안된다.

다음으로 작은 가중치 2인 간선을 연결하고, 3을 연결하는데,

1 과 2 를 연결할 때 마찬가지로 싸이클이 생기기 때문에 연결하면 안된다.

이제 가중치가 4인 간선을 연결해야 하는데 2와 4를 연결하면 싸이클이 생기기 때문에 역시 연결하면 안되고,

3과 8도 싸이클 때문에 연결하면 안된다.

이제 최소 스패닝 트리가 완성했다. 크루스칼 알고리즘은 의외로 이렇게 간단하게 동작한다.

하지만 눈으로 보면서 따라가면 간단하지만, 이것을 프로그래밍으로 어떻게 구현할지에 대해 생각해보면

2가지 생각해볼 이슈가 생긴다. 

① 간선의 가중치를 어떻게 작은 순서대로 정렬할까 ?

② 간선을 한개 그릴 때 마다 싸이클이 생기는지 안생기는지 체크해야 하는데 어떻게 할까 ?

이 두가지 이슈를 해결하는 것이 크루스칼 알고리즘을 구현하는 핵심이다.

---

이제 위의 트리에서 간선을 그었을 때 싸이클이 생기는 조건을 생각해보자.

밑에 그림들은 같은 그룹의 트리내에서 두 가지 노드를 연결하면 간선이 생기는 경우들이다.

여기서 하나의 결론을 도출해 낼 수 있는데, 하나의 트리 내에서 간선이 하나라도 추가되면

싸이클이 무조건 생긴다는 것이다.

이것을 아까 예제에 적용해 보면, 처음의 그래프에서는 각각의 노드를 독립된 트리라고 본다.

이제부터 작은 가중치의 간선부터 연결하자. (위의 경우는 1)

5를 2 -- 3 -- 7 에 연결한다고 해보면

2 -- 3 -- 7 하나의 트리이고, 5 역시 하나의 독립된 트리이기 때문에 연결할 수 있다.

다음 크기인 가중치가 2인 간선을 연결한다고 해보면,

 2 -- 3 -- 7 -- 5 와 8을 보면 둘다 연결이 되지 않은 독립된 트리이기 때문에 연결할 수 있다.

1 -- 6 과 나머지 2 -- 3 -- 5 -- 7 -- 8 역시 연결하려고 하는데,

둘은 다른 트리이기 때문에 연결할 수 있다.

여기에서 5와 7을 연결하려고 해보면, 두 노드는 같은 트리내에 포함되어 있기 때문에

연결할 수 없다.

---

싸이클이 생기는지 안생기는지 판단하기 위해서 또 알아야 할 개념이 Disjoint Set 이라는 자료구조 이다.

DisJoint Set은 위와 같이 2가지 기능을 할 수 있다.  첫 번째 기능은 두 정점을 하나의 그룹으로 묶는 것인데,

만약에 1 ~ 8 까지 모두 독립된 노드라고 가정하자.

이 때 1 과 2 를 하나의 그룹으로 묶자고 해보자. 그러면 1과 2가 같은 그룹에 포함되는지 안되는지 검사를 한다.

만약에 1과 2가 같은 그룹에 포함되어있지 않다면, 1과 2를 하나의 그룹으로 묶는다.

3과 4도 묶기 위해서 같은 그룹에 포함되어 있는지 안되어 있는지 검사를 하고 묶는다.

두 번째 기능은 두 정점이 같은 그룹 내에 속하는지 안속하는지 물어보는 기능이다. 위와 같은 상태에서

3과 4가 같은 그룹내에 속하는지 물어보면 YES라고 답한다.

1과 3이 같은 그룹내에 속하냐고 물어본다면 NO라고 답한다.

1과 3을 하나의 그룹으로 묶는다고 하면

1의 자식인 2와 3의 자식이 4까지 함께 묶인다. Disjoint Set은 이러한 기능과 특징을 가지고 있다.

---

Disjoint Set의 기능을 트리에 적용해보자. 1과 2를 하나의 그룹으로 묶으면

1의 자식으로 2간 트리가 만들어진다.

3과 4를 하나의 그룹으로 묶으면

3의 자식으로 4가 들어간 트리가 만들어진다.

이 상태에서 만약에 4와 6이 같은 그룹내에 속한다고 물어본다면 4의 루트노드인 3과 6의 루트노드인 6을

비교하여 같은 그룹이 아니라고 한다.

2와 4가 같은 그룹내에 속하는지 물어보면

2의 루트인 1과 4의 루트인 3을 비교해서 같은 그룹내에 속하는지 본다.

만약에 1과 4를 하나의 그룹으로 합친다고 한다면

1의 루트인 1과, 4의 루트인 3을 선택하여

1의 자식으로 3이 들어가게 된다.

이 상태에서 2와 4가 같은 그룹내에 속하냐고 물어본다면

2와 4의 루트인 1을 비교하여 같은 그룹내에 속한다고 알려준다.

이렇게 Disjoint Set을 트리에 적용하여 사용할 수 있다.

---

이제 크루스칼 알고리즘을 구현하는데 필요한 개념들을 정리 했으므로 구현할 때 적용해보자.

위의 사진에서 5와 7을 연결하려고 시도한다면 서로의 루트노드가 같기 때문에, 즉 같은 그룹이기 때문에

연결하지 못한다. 연결하게되면 싸이클이 생기기 때문이다.

그래프와 Disjoint Set을 동시에 보면 이해가 더 쉽게 된다. 가장 작은 가중치인 1을 연결하기 위해

1과 6을 연결하려고 할 때, 1과 6이 같은 트리에 속하는지 물어보고,

같은 트리에 속해있지 않으므로 두 정점은 간선으로 연결할 수 있다. 그리고 Disjoint Set에서 1과 6을 같은 그룹으로 묶는다.

다음으로 가중치 1짜리 간선을 다 연결하고 보니 마지막으로 5와 7을 연결해야 하는데,

Disjoint Set에서 7과 5의 루트노드는 2로 같기 때문에 둘은 같은 트리내에 존재한다고 판단하여

연결하지 못한다.

가중치 1 짜리 간선을 다 연결 했으므로 다음으로 2 짜리 간선을 연결하고,

가중치 3짜리 간선을 연결하려고 노드 2와 노드 1을 연결하려고 하는데,

1의 루트는 1이고 2의 루트는 2이므로 두 개의 노드는 서로 다른 트리에 있다고 판단하여

2와 1을 연결해서 최소 스패닝 트리를 완성한다.

이러한 원리와 과정을 통해 크루스칼 알고리즘을 사용하여 MST를 만든다

출처 : Algorithm LABS