[Do it!_Algorithm with Python] 6.2 Minimum Spanning Tree

Source: inflearn 'Do it! 알고리즘 코딩테스트 with python'

 

 

최소 신장 트리란, 그래프의 모든 노드를 한번씩 방문할 때, 거쳐가는 edge들의 가중치의 합이 최소가 되도록 하는 트리이다.

 

▪️특징

- 트리이므로 사이클을 포함하지 않는다.

 (만약 모든 노드를 연결해서 순환되는 구조가 만들어지면, 최소의 가중치가 될 수 없다. 하나의 엣지를 제거하더라도 모든 노드를 거치는 경로를 만들 수 있기때문이다.)

- N개의 node가 있으면, MST를 구성하는 edge의 수는 N-1개이다.

- 구현하는 방법은 크루스칼 / 프림 알고리즘이 있다.

 

* 크루스칼 알고리즘

크루스칼 알고리즘

 

 

* 프림 알고리즘

 

프림 알고리즘

 

크루스칼은 처음부터 모든 간선의 가중치를 오름차순으로 정렬한 후에 작은 가중치의 간선부터 연결하지만,

프림 알고리즘은 처음 시작한 노드의 인접 간선 중, 가중치가 가장 작은 간선을 선택하면서 연결한다는 점이 다르다.

 

이번 포스팅에서는 크루스칼 알고리즘을 살펴보자

 

 

▪️과정

먼저 다음 두가지가 필요하다

- 그래프를 표현할 edge list : MST는 데이터를 노드가 아닌, 가중치가 담긴 edge 중심으로 저장해야 한다.

- Union-find list : 사이클이 생기는지 판별하기 위해서 사용

 

 

1) 엣지 리스트로 그래프 구현 -> Union-Find list 초기화하기

 

 

2) 그래프 데이터를 '가중치 기준'(오름차순) 으로 정렬하기

 

 

 

3) 가중치가 낮은 edge 부터 연결 '시도'하기

 

여기서 왜 '시도'한다 라는 표현을 썼냐면, 매번 연결할때마다 사이클이 생기는지 확인해야하기때문이다.

사이클이 안생기는 것이 보장돼야 연결이 가능하다.

위 그림에서 처음에는 아무 노드도 연결되어 있지 않았다. 이 상태에서 가장 가중치가 낮은 첫번째 엣지 1 연결을 시도해보자.

find(4), find(5) 로 각 노드의 대표노드를 확인한다. union-find list를 포면 각각 4, 5이므로 대표 노드가 서로 다르다.

즉, 서로 연결되어 있지 않다는 뜻이다. 이 상태에서 두 노드를 연결하면 사이클이 생기지 않는다.

따라서 node 5의 union-find list의 값을 4로 업데이트 해주어 union(연결)을 수행한다.

 

하지만 만약 node 4와 node 5의 대표 노드가 같았다면 이 둘을 연결하는 순간 사이클이 생성되므로 해당 간선을 연결해주면 안된다.

 

 

 

4) 간선의 개수가 N-1이 될때까지 반복한다.

 

이 과정을 간선의 개수가 N-1 (여기서는 4개)가 될때까지 반복한다.

단, 연결할때마다 매번 사이클이 형성되는지 체크해주는 것을 잊지 말아야한다.

 

위 그림에서 세번째를 보면, node 2와 node 5를 연결해주려고 시도했더니, find 수행 결과 서로 대표 노드가 같은 것을 감지했다.

그래프를 보면, 2와 5를 연결할경우 사이클이 형성된다. 따라서 이 엣지는 생략하고 다음으로 넘어간다.

마지막 노드 1과 2는 서로 대표노드가 다르므로 간선을 연결하게 되고, 총 간선의 개수가 4개가 되었으므로 종료한다.

 

 

6) 총 간선 비용을 출력한다

최종적으로 만들어진 트리의 모든 간선의 가중치를 합하여 최소비용을 출력해준다.

3+8+4+2 = 17

 

 

 

 

 

내용은 어렵지는 않지만 구현이 조금 까다롭다.

그래프를 엣지리스트로 저장하기때문에 생소할 수 있다. 

union-find 알고리즘 또한 구현해야하기때문에  백준 예제문제로 연습해보자!