최소 신장(스패닝) 트리(minimum spanning tree)

SEUNGHWANLEE·2021년 10월 19일
0

Algorithm

목록 보기
9/14
post-thumbnail

Spanning Tree

우선, Spanning Tree는 무엇일까?

그래프 내의 모든 정점을 포함하는 트리를 의미한다.

간선의 수(edges)가 가장 적게, 최소 연결을 해야하는 트리

  • N개의 정점(Vertex)를 갖는 그래프
  • 최소 간선의 수(Edges)N-1

다시말하자면 그래프에서 일부 간선들로 이루어진 트리를 말한다

  • 전체 그래프의 모습
  • 일부 간선들로 이루어진 트리의 모습

최소 스패닝 트리(minimum spanning tree) 란?

앞서 설명한 Spanning Tree 중에서 사용된 간선들의 가중치의 합이 최소인 트리를 의미한다.

모든 정점들을 가장 적은 수의 간선과 가중치의 합으로 연결하는 것이다.

특징

  • 간선의 가중치 합이 최소
  • N개의 정점이라면 반드시 N-1개의 간선
  • 사이클(Cycle)이 포함되면 안됨

구현 방법

여러 포스팅을 읽어보면서 느낀 점은 비교할 간선이 많은 경우에는 Prim 알고리즘을, 간선이 비교적 적은 경우에는 Kruskal을 사용해서 해결한다고 한다. 그 외 다익스트라와 같이 지점 to 지점으로 최소의 가중치를 가지고 있는 path를 찾아낼 수도 있지만 이번 포스팅에서는 많이 다뤄지는 Kruskal과 Prim에 대해서 다뤄보고자한다.

  • 간선이 많은 경우, Prim
  • 간선이 적은 경우, Kruskal

Kruskal 알고리즘

생각보다 신기했던 알고리즘, Union과 Find의 조화

💡 조건

  • 모든 정점(Vertex)이 포함
  • Cycle(사이클)이 존재해서는 안됨
  • 정점(Vertex)가 N개일 때 간선의 갯수(Edges)는 N-1
  • 이때 더해진 가중치의 합은 최소가 되어야함

💡 과정

  1. 그래프의 간선들을 가중치를 기준으로 오름차순 정렬
    👉 0번째 index가 가장 작은 원소를 갖게끔
  2. 정렬된 간선 list에서 순서대로(0부터) Cycle을 형성하지 않는 간선을 선택
    👉 가장 낮은 가중치(0번째)를 먼저 선택
    👉 사이클을 형성하는 간선 제외
  3. 선택한 간선을 지금까지 형성된 트리에 추가 및 가중치 합산

과정 예시

예를 들어서 아래와 같은 그래프가 있다고 해보자

총 정점은 모두 5개로 정점마다 a,b,c,d,e 라고 이름이 붙어져 있으며 간선 위에는 각 가중치가 적혀있다. 이때 가중치를 기준으로 오름차순 정렬을 해보면 아래와 같이 정렬할 수 있다.

가중치간선
1a-b
1c-e
2c-d
3a-d
4a-c
4d-e

형성된 스패닝 트리가 없다면 가장 위에 있는 a-b 간선을 트리에 추가해준다. 그리고 다음으로 가중치가 작은 간선은 c-e가 되는데, 이때 c-e간선이 사이클을 만드는지 확인을 해야한다.

그렇다면 사이클을 형성하는지는 어떻게 알 수 있을까? Union-Find 자료구조를 사용하면 된다.

💡 Union-Find

Union-Find 자료구는 Disjoint Set(서로소 집합, 공통원소가 없는 두 집합)을 표현하는 자료구조이다.
두 집합을 먼저 병합을 한다고 해서 Union, 그리고 집합 원소가 어디에 속해있는지 찾는다고 해서 Find이다.

Union-Find를 통해서 사이클을 형성하는 지 알아보자!
먼저, 스패닝 트리가 형성되기 전인 상황으로 돌아간다고 가정을 하고 parent 배열을 만들어 본다

childabcde
parentabcde

위와 같이 생긴 서로소 집합을 만들 수 있다. 간선을 선택하기 전인 위에 배열은 각자의 부모를 본인으로 설정해둔 것이다.

  1. 간선 a-b를 선택한 이후의 모습
childabcde
parentab→acde

b의 부모가 a로 바뀌었다.
바꿔준 이유는 뭘까? a와 b가 서로 각자 다른 노드를 가리키고 있었고, 이 상황에서 a-b 간선을 선택해줬기 때문에 a와 b는 이제 같은 집합 내 속해있다고 값을 변경해주어야한다. 그러므로 각자 다른 부모 노드를 가리키고 있을 때 두개의 노드 모두 작은 값을 가진 부모를 가리키게 하므로 같은 집합 내 속하게 만드는 것이다.

각자 가리키는 부모가 다를 때, 작은 값의 부모로 통일시켜준다.

이렇게 되면 그래프가 아래와 같이 구분 지어 질 수 있다.

그룹 1그룹 2그룹 3그룹 4
a, bcde
  1. 간선 c-e를 선택한 이후의 모습
childabcde
parentaacde→c

...

계속해서 같은 작업을 반복하게되면 마지막에는 아래와 같은 표와 함께 탐색이 종료된다.

childabcde
parentaacc→ac

탐색이 종료되는 이유는 연결된 간선의 갯수가 모든 정점의 갯수 - 1개와 같기 때문이다.

Cycle 형성이 되는 경우?

만약에 간선 d-e가 가중치 3을 갖고 있었다면, a-d보다 우선순위가 높았을 것이며 아래와 같이 그래프가 이루어졌을 것이다.

가중치간선
1a-b
1c-e
2c-d
3d-e
4a-d
4a-c

이때는 parent 배열이 아래와 같이 되어있을텐데,

childabcde
parentaaccc

이때 d와 e를 선택하려고 하면 서로 같은 부모를 가리키고 있기 때문에 사이클이 형성되는 점을 알 수 있다.

🎯 이렇게 간선을 선택할 때 ① 사이클을 형성하는 지 확인 ② 선택한 간선의 갯수가 모든 정점의 갯수 -1 개인지 확인 하면서 작은 가중치를 더해가다보면 Kruskal 알고리즘을 적용해서 문제를 해결할 수 있다.

Tips

Find 구현 시 참고할 점

찾으려는 노드의 부모가 어느 집합에 소속되어있는지를 알아내야하는 게 중요하다.

위와 같이 4의 부모가 2이지만, 2는 또 1에게 속해있기 때문에 이런 점을 주의해야한다. 따라서 while문이나 재귀를 이용해서 잡아주는 것이 좋다.

예시코드)

def find(parent, node):
	if parent[node] == node: return node
    	else: find(parent, parent[node])

Prim 알고리즘

지정한 정점부터 출발, 트리를 단계적으로 확장
정점을 선택하면서 이전 단계에서 만든 트리를 확장해나가는 방식

💡 과정

  1. 첫 트리는 시작점만이 포함
    👉 [root]
  2. 만들어진 트리의 노드와 인접한 정점들 중에서 가장 낮은 가중치 값을 가진 간선과 연결된 정점을 선택
    👉 가장 낮은 가중치를 가진 간선을 선택
  3. 트리가 N-1개의 간선을 가질 때 까지 반복

Tips

  • 간선의 가중치를 기준으로 minheap으로 스패닝 트리를 구성하면 수월함
    👉 root에는 항상 작은 가중치가 오기 때문에, 이어지는 경로는 그래프를 통해서 확인

관련 문제

👉 백준-최소 스패닝 트리
👉 백준-네트워크 연결
👉 백준-도시 분할 계획

참고문헌

https://chanhuiseok.github.io/posts/algo-33/
https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html

profile
잡동사니 😁

0개의 댓글