최소 신장 트리가 뭘까?

최소 신장 트리는 신장 트리 중 가중치가 가장 작은 그래프이다.

그럼 신장 트리가 뭘까?

신장 트리

신장 트리는 그래프 내에 있는 모든 노드를 연결하고 사이클이 없는 그래프를 이야기한다.

아래의 예시를 한번 보자.

이 그래프에서 신장트리는

이것도 있을 수 있고

이것도 있을 수 있다

신장 트리는 매우 많이 존재할 수 있는데 그중에서 가중치가 가장 작은 트리가 바로 최소 신장 트리이다.

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

위에서 최소 신장 트리가 뭔지 알아봤다. 그럼 어떻게 최소 신장 트리를 어떻게 구할 수 있을까?

최소 신장 트리를 구하는 방법은 프림 알고리즘, 크루스칼 알고리즘 총 2가지가 있다.

프림 알고리즘

프림 알고리즘은 매 순간 최선의 조건을 선택하는 그리디 알고리즘을 바탕으로, 가중치가 적은 간선을 선택하며 최소 신장 트리를 만든다.

좌상단 노드에서부터 시작해서 프림 알고리즘을 사용하여 최소 신장 트리를 만들어보자

먼저 시작 노드에서는 3가지 길이 각각 1, 6, 5의 가중치가 있다.

프림 알고리즘은 매 순간 가중치가 적은 간선을 선택해 최소 신장 트리를 만들기 때문에 우리는 1의 가중치를 가진 간선을 선택한다.

다음 노드는 가중치가 2인 간선밖에 없다. 연결해주자

다음 노드는 가중치가 3과 6의 간선을 가지고 있다. 가중치가 작은 3의 간선과 연결해주자.

마찬가지로 가중치가 작은 간선을 연결해주자

또 가중치가 작은 노드를 연결해주자

모든 노드가 연결되었다. 연결되지 않은 간선을 제거해주자

프림 알고리즘을 사용하여 최소 신장 트리를 만들어 봤다. 그럼 크루스칼 알고리즘은 어떻게 최소 신장 트리를 만들까?

크루스칼 알고리즘

크루스칼 알고리즘은 프림 알고리즘과 같이 그리디 알고리즘을 기반으로 한다. 하지만 프림 알고리즘과 다른 부분이 있는데, 그건 간선을 선택하는 방식이다.

프림 알고리즘에서는 노드에서 가중치가 작은 간선을 골라 연결했다면 크루스칼 알고리즘에서는 간선의 가중치가 작은 순서로 연결한다.

무슨 소리냐? 아래의 예시를 한 번 보도록 하자.

현재 이 그래프에서 간선의 가중치는 { 1, 2, 6, 5, 1, 4, 2, 3 } 이렇게 8가지 존재한다.

여기서 가중치가 가장 작은 1의 간선부터 연결한다는 소리다.

그다음으로 가중치가 가장 작은 간선을 연결하고

또 연결하고

또 연결하고

또 연결하다 보면

모든 노드끼리 연결이 된다.

마지막으로 연결이 되지 않은 간선을 제거해주면

최소 신장 트리가 만들어진다.