오늘은 최소신장트리에 대해서 알아보겠습니다!!
그 전에 신장 트리에 대해서 알아봐야하는데, 이는 이전 그래프 관련 글에서 다루었으므로 생략하겠습니다.
최소 신장 트리
최소 신장 트리에서는 간선에 가중치가 존재합니다. 실생활에서 쓰이려면 두 정점 사이의 거리라고 해석해도 될 것 같습니다.
저희는 이러한 가중치를 최소화하고 싶습니다.
그래서 간선의 가중치가 최소인 신장 트리를 생각하게 되었고 이를 최소 신장 트리라고 합니다.
최소 신장 트리를 구성하기 위해 쓰이는 알고리즘은 그리디 알고리즘입니다.
그리디 알고리즘은 매순간 현재로써 가장 좋은 선택을 한다는 의미에서 욕심쟁이 알고리즘이라고 합니다.
이러한 그리디 알고리즘에 대한 개념은 최소 신장 트리를 구현한 알고리즘을 이해하면서 차차 알아가실 수 있습니다.
이러한 그래프가 있습니다. 이 그래프에서 우리는 신장 트리를 찾습니다.
다양한 신장 트리가 있겠지만, 우리는 아래와 같은 신장 트리를 찾을 수 있습니다.
신장 트리의 특징은 정점이 n개 일 때, 간선이 n-1 개임을 의미합니다. 따라서 위와 같은 모양이 나오게 되죠.
그럼 이제 최소 신장 트리를 확인해봅시다.
이러한 가중치를 가지는 그래프가 있다고 하면 최소 신장 트리 중 하나는 아래와 같을 것입니다.
이제 다음 글에서는, 이러한 최소 신장 트리를 어떻게 찾을 수 있을지에 대해서 알아보겠습니다! 감사합니다.
'CS > Algorithm' 카테고리의 다른 글
| [알고리즘] 강 연결 성분이란? - Kosaraju 알고리즘 (3) | 2023.10.15 |
|---|---|
| [알고리즘] 강 연결 성분이란? - Tarjan 알고리즘 (1) | 2023.10.14 |
| [알고리즘] 이중 연결 성분이란? (1) | 2023.10.13 |
| [알고리즘] 위상정렬이란? (0) | 2023.10.13 |
| [알고리즘] BFS란? (2) | 2023.10.12 |