최소 신장 트리(MST), 크루스칼 알고리즘 (kruskal)

학교에서 배웠었는데 알고리즘 문제에 필요해서 다시 한번 정리. 

 

Union-Find 알고리즘 : (https://tose33.tistory.com/614)

 

- 크루스칼 알고리즘 

최소의 비용으로 모든 노드를 연결하는 알고리즘

- 신장 트리 (Spanning Tree)

1) 그래프의 모든 정점을 포함

2) 싸이클을 형성하지 않음  -> 이 조건에 의해 정점의 갯수가 n개 일때, 간선의 갯수는 무조건 n-1개 

 

- 최소 신장 트리 (Minimum Spanning Tree, MST) 

신장 트리이면서 가중치(간선)의 합이 최소가 되는 트리 

 

 

- 최소 신장 트리 구하는 방법 

1. 간선들의 가중치를 기준으로 오름차순 정렬한다 

2. 가중치가 작은 간선부터 사이클을 형성하지 않는다면 잇는다 

3. 간선의 갯수가 정점의갯수-1개가 됐다면 최소 신장 트리 완성 

 

- 사이클을 형성 하는지 아닌지 판단법 

-> 각 정점의 부모 정점이 같다면 싸이클.

최초에 각 정점은 자기 자신을 부모 정점으로 갖는다.

작은 가중치를 갖는 간선부터 잇는데 잇는 두 정점의 부모가 같다면 사이클 이므로 잇지 않는다. 

 

 

 

FindParentNode에서 재귀적으로 부모 노드를 찾는데, return 문에서 parentNode[node] = FindParentNode(parentNode[node]) 이런 식으로 재귀하면서 값을 저장해줘야 시간을 줄일수 있다. 

 

 

 

최종적으로 parentNode는 모두 0이 된다. 

모두 0 노드를 부모(루트) 노드로 갖게된다. 

 

 

 

크루스칼 알고리즘으로 MST가 성공적으로 만들어졌는지 판별 

 

2022.05.21 

https://www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

 

이 문제를 풀다가 잘못된 점을 수정한다. 

위에서 최종적으로 parentNode 배열은 모두 가장 작은 노드값인 0을 갖게 된다고 했었는데 틀렸다.

부모 노드의 판별은 재귀적으로 그떄그때 판단하기 때문에, 모든 노드들이 연결된 MST가 완성된다고 하더라도 최종적으로 parentNode 배열이 모두 같은 값이 되지는 않는다.

 

예를들어 아래와 같은 그래프가 MST가 있다고 하자. 

 

1 ---- 2 ---- 3

            |

           4 

 

이때 최종적으로 parentNode[] 배열은 다음과 같이 된다 

Node:	1	2	3	4
Parent:	1	1	2	2

 

노드4의 부모를 판별할땐 재귀적으로 노드4의 부모노드인 2로가고 2의 부모노드인 1로 가기 때문에, 

노드 4의 부모노드는 1이다. 

 

따라서 크루스칼 알고리즘으로 최소 스패닝 트리 만들기를 시도했을때 성공했는지 여부는 parentNode 배열이 모두 같은 값인지로 판단하는 것이 아닌 (내가 이렇게해서 틀림) 두 노드를 잇는 Union 과정이 몇번 일어나는지를 계산한후에, 

Union 횟수 +1 = 총 노드의 갯수 여야 MST가 성공적으로 만들어 진 것이다. 

(정확히 말하면 최종적으로 간선의 갯수는 노드의 갯수보다 하나 적어야 한다)