신장트리(Spanning tree)?
신장트리는 그래프에서 모든 정점이 연결되어있고, 그래프에 싸이클이 존재하지 않는(tree의 조건) 그래프를 말합니다.
- 싸이클 : 그래프의 특정 정점에서 출발하여 다시 처음 출발했던 곳으로 되돌아 갈 수 있으면 사이클이 있다고 합니다.
위와같은 그래프에서 싸이클이 존재하지 않고 모든 정점을 연결하는 경우는 아래와 같을 수 있습니다.
최소신장트리?
위와같은 신장트리에서 간선의 가중치의 합이 최소가되는 신장트리를 최소신장트리(Minimum Spanning Tree)라고 합니다
크루스칼 알고리즘?
크루스칼 알고리즘은 위의 최소신장트리를 구하는 알고리즘입니다.
먼저 최소 비용으로 모두 연결만 시키면 되기 때문에 가중치의 값을 기준으로 오름차순 정렬합니다.
과정은 이렇습니다
1.정렬된 가중치 순서에 맞게 간선을 그래프에 포함시킵니다.
2.포함시키기 전에 싸이클이 형성되는지 확인합니다.
3.싸이클이 형성되는 경우 간선을 포함시키지 않습니다.
그럼 세부 과정을 그림으로 확인해 보겠습니다.
1) A - D 의 간선을 추가할 경우 싸이클이 존재하지 않으니 그래프에 포함시킵니다.
2) C - E 의 간선을 추가할 경우 싸이클이 존재하지 않으니 그래프에 포함시킵니다.
3) D - F 의 간선을 추가할 경우 싸이클이 존재하지 않으니 그래프에 포함시킵니다.
4) A - B 의 간선을 추가할 경우 싸이클이 존재하지 않으니 그래프에 포함시킵니다.
5) D - E 의 간선을 추가할 경우 싸이클이 존재하지 않으니 그래프에 포함시킵니다.
6) B - G 의 간선을 추가할 경우 싸이클이 존재하지 않으니 그래프에 포함시킵니다.
7) B - C의 간선을 추가할 경우 싸이클이 존재하게되니 그래프에 포함시키지 않습니다.
8) D - B의 간선을 추가할 경우 싸이클이 존재하게되니 그래프에 포함시키지 않습니다.
9) E - G의 간선을 추가할 경우 싸이클이 존재하게되니 그래프에 포함시키지 않습니다.
10) F - G의 간선을 추가할 경우 싸이클이 존재하게되니 그래프에 포함시키지 않습니다.
그림으로 확인해보니 더 간단하게 느껴지네요!
하지만 이 알고리즘을 코드로 구현하는 경우는 조금 까다로울 수 있습니다.
구현 과정에서 서로소 집합(Disjoint Set), Union-Find라는 개념이 쓰이는데요 이부분은 다음 포스팅에서 알아보도록 하겠습니다.
감사합니다.
'알고리즘' 카테고리의 다른 글
| [백준 15683] 감시(BOJ 15683)(삼성 SW 역량 테스트 기출) (0) | 2019.10.17 |
|---|---|
| [백준 14499] 주사위 굴리기(BOJ 14499)(삼성 SW 역량 테스트 기출) (0) | 2019.10.15 |
| [백준 10942] 팰린드롬(BOJ 10942)[DP] (0) | 2019.08.14 |
| [백준 2828] 사과 담기 게임(BOJ 2828) (0) | 2019.08.06 |
| [백준 9465][DP] 스티커 (BOJ 9465) (0) | 2019.06.27 |
