최소 신장 트리(Minimum Spanning Tree) 자료구조

최소 신장 트리(Mininum Spanning Tree) 자료구조

그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 신장 트리

 

* 신장 트리(Spanning Tree) : 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

 

 

그래프(Graph) 자료구조

그래프(Graph) 자료구조

 

 

최소 신장 트리 특징

• 사이클을 포함하지 않는다. (사이클이 포함되면 가중치의 합이 최소가 될 수 없기 때문)
• N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N - 1개다.
• 간선의 개수가 E개일 때, 시간 복잡도 : O(ElogE)

 

 

최소 신장 트리 핵심 이론

1. 에지 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화한다.

[ 예시 ]

 

- 최소 신장 트리는 데이터를 노드가 아닌 에지 중심으로 저장하므로 인접 리스트가 이닌 에지 리스트의 형태로 저장한다.

- 사이클 처리를 위한 유니온 파인드 배열의 인덱스를 해당 자리의 값으로 초기화한다.

 

 

2. 그래프 데이터를 가중치에 따라 오름차순으로 정렬한다.

[ 예시 ]

 

 

3. 가중치가 낮은 에지부터 하나씩 확인하며 현재의 에지가 사이클을 발생시키는 지 확인한다.

[ 예시 ]

 

① 가중치가 낮은 에지부터 차례대로 연결을 시도한다.

② find 연산을 수행해 선택된 두 노드의 대표 노드가 서로 다를 경우만 union 연산을 수행해 연결한다.

- 대표 노드가 같은 경우, 두 노드를 연결했을 때 사이클이 발생한다.

  - 사이클이 발생하는 경우, 최소 신장 트리에 포함시키지 않는다. 

- 대표 노드가 같지 않은 경우, 두 노드를 연결했을 때 사이클이 발생하지 않는다.  

  - 사이클이 발생하지 않는 경우, 최소 신장 트리에 포함시킨다.

 

 

4. 모든 에지에 대하여 3번의 과정을 반복한다.

[ 예시 ]

 

전체 노드의 개수가 N개이면 연결한 에지의 개수가 N - 1이 될 때까지 과정 3을 반복한다.

 

[ 예시 ]

노드 2와 노드 5의 루트가 이미 동일한 집합에 포함되어 있으므로 신장 트리에 포함하지 않아야 한다.

 

 

5. 총 에지 비용을 출력한다.

 

[ 예시 ]

 

에지의 개수가 N - 1이 되면 알고리즘을 종료하고, 완성된 최소 신장 트리의 총 에지 비용을 출력한다.

 

• 에지의 개수 N - 1 : 최소 신장 트리는 일종의 트리(Tree) 자료구조이므로, 최종적으로 신장 트리에 포함되는 에지의 개수가 '노드의 개수 - 1'개이다.

 

[ 예시 ]

총 에지 비용 = 2 + 3 + 4 + 8 = 17

 

 

 

 

 

* <Do It! 알고리즘 코딩테스트 with C++편>, <이것이 취업을 위한 코딩 테스트다 with 파이썬>을 참고하였습니다.