크루스칼 알고리즘 기반의 최소비용신장트리

크루스칼 알고리즘 기반의 MST 구현에 있어서 2가지 방법이 존재한다.

1. 선택 

2. 삭제

우선 가장 먼저 해야할 것은 가중치를 정렬하는건데, '선택'을 하냐 '삭제'를 하냐에 따라서 정렬 방법이 틀리며, 구현방법 또한 틀리다.

[선택을 했을 경우 방법]

1. 가중치는 오름차순 정렬한다.

2. find + union 알고리즘을 사용한다. (cycle을 감지하기 위해)

find + union 알고리즘을 처음 접했을 때, 도대체 이게뭔가? 단순히 배열안에 정수값을 넣는건데, 도대채 어떻게 이걸 트리라고 볼수있는가? 처음에 이론을 접했을 떄는 50%정도만 이해됬다. 그리고 디버깅을 해보고 완전히 이해했다. 

만약 이론으로 이해가 안되면 디버깅을 해보자. 그럼 100% 이해 할 수 있다.

가장 먼저 알고 들어가야할 것이, find + union 알고리즘에서 초기화를 무조건 해야하는데 이때 각 요소(element)는 루트노드라고 가정하는 것 이다.  그리고 이 루트노드는 음수이다.

초기화를 진행 한 뒤, 정렬되있는 가중치들에서 '선택' 을 하게된다. 

처음에는 아무나 루트노드가 될 수 있다. 그래서 루트노드가 뭐냐? 는 중요하지가 않다. 루트노드에 적혀있는 기록(값)이 중요한거다.

  A

B  C

라는 트리가 있을때 A가 루트노드이며 이안에 기록되있는 값은 -3이다. 자신을 포함하고, 밑에 B,C까지포함해서 -3(루트노드는 반드시 음수표시)이다.

이때 B와 C는 A인덱스(상수화되있다면 0)값이 들어가있다. 그래서 자식노드는 자신의 부모노드(루트노드아님)의 인덱스값을 가지고있는것이다. 반면에 루트노드는 자식노드의 개수를 가지고있다.

아까 말했듯이, 처음에 루트노드를 아무거나잡고(들어오는순대로) 진행하다가, 어떤 정점 u와 어떤 정점v의 간선을 선택하려고하는데, 두개의 루트노드를 추적해보니 루트노드가 틀리다면, 이때 병합이 일어난다. 어떤 루트노드의 값이 더작냐(노드수가더많은것)에 따라서, 흡수(?)가 되는데, A라는 루트노드와 B라는 루트노드가 있다고 가정 했을 때, A가 더 값이작다면(더노드수가많다면) A의 값에 B의 값을 더한다. 더하는 이유는 B가 A에게 흡수되기때문에 기존에 A가 지니고있던 자식노드들의개수에서 B가갖고있던 자식노드들의 개수를 더해줘야 하기때문이다. 그다음, B에는 A의 인덱스를 대입(여기서는 더하는게아님)한다.

이렇게 반복해서 연산하면 cycle을 감지 할 수있게 된다. 근데 마지막으로 한가지 더 중요한것은, MST에서는 싸이클만 감지하면 되는게아니라, 어느시점에서 MST의 조건에 부합하게되면 그 이상 동작을 하지않고 함수를 종료할 수 있어야 한다. 만약 이렇지않다면 cycle은 다 잡을수있지만 결과적으로 봤을때 불필요한 간선이 몇개 더 추가 될수가 있기때문에 반복문에 MST의 조건(간선 = 정점-1)을 걸어둔다.

 

[삭제를 했을 경우 방법]

1. 가중치는 내림차순 정렬이다.

2. 간선을 삭제하는식으로 간선을 줄여나간다

정렬된 간선들을 가지고 간선들을 실제로 삭제해나간다. 이때, 삭제를 한뒤, 점검을 해봐야한다. 삭제를 하고나서 두 정점간의 또다른 간선이 있는지 없는지 체크하는 점검이다.

삭제를 했는데 만약 두 정점을 더이상 연결하는 간선이 없다면 다시 복구시켜야한다. 이때 두 정점간에 연결된 간선을 찾는 탐색은 DFS를 주로 쓴다. 그래서 DFS로 탐색했는데 연결된 간선이없으면 다시 복구시키며, 연결된 간선이 있다면 계속진행해나간다.

역시 이때도 반복문의 조건은 '선택' 방법과 동일하다.

시간복잡도는 find + union 알고리즘이 삭제하는방식 보다 빠른것으로 알려져있다. (삭제하는방식은 DFS를 쓰기떄문에 느림)

하지만, 실제로 어떤그래프에서 MST연산을 한뒤의 그래프를 보고싶다면(단순히 가중치합을보는게아니라) 삭제연산을 쓰는게 훨씬더 비용이적게든다. 왜냐하면 원래기존의 그래프에서 간선들만 삭제하기때문에 MST연산을 끝낸뒤, 그대로 DFS나 BFS로 모든 정점을 탐색해보면 실제로 (MST연산으로인해)줄어든 그래프를 볼 수 있지만, find + union의 경우에는 간선을 '선택' 해나가는 방식이기때문에, MST연산후에 그 그래프를 보고싶다면 선택된 간선으로 다시 그래프를 구성 해야 한다.

마지막으로 , 크루스칼 알고리즘에서 정렬방법에는 보통 우선순위큐(힙)을 많이 쓴다.

하지만 구지 힙을 쓰지 않아도된다. 가중치들만 쫙 뽑아내서 정렬알고리즘을 써서 정렬시킨뒤 진행해도 상관없다.