강의 시간에 분명 들은 내용이지만...
문제를 풀려니 하나도 기억이 나지 않아 이렇게 정리를 하게 되었다.
MST를 다루기 전 기초 개념들부터 간단하게 짚고 넘어가보자.
그래프
- 노드와 간선으로 구성된 한정된 자료구조로 연결된 객체 간의 관계를 표현할 수 있는 자료구조이다.
- 방향이 있을수도(유향 그래프), 없을수도 있으며(무향 그래프) 부모-자식의 관계가 존재하지 않는다.
- 순환일수도, 순환이 아닐 수도 있다.
- 노드-노드를 잇는 간선에 가중치가 주어질 수도 있으며(가중 그래프), 가중 그래프 중 유향 그래프를 '네트워크'라고 한다.
트리
- 그래프의 일종으로, 회로(cycle)가 없고 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프
- 최상위 노드를 루트 노드라 하며 부모-자식 관계가 존재한다.
- 노드가 N개인 트리는 항상 N-1개의 간선을 갖는다.
신장 트리
- 그래프 내의 모든 노드를 포함하되 사이클이 존재하지 않음.
- 하나의 그래프에 대해 여러 개의 신장 트리가 존재할 수 있다.
최소 신장 트리
개념
- 신장 트리 중 포함된 간선들의 가중치의 총 합이 최소인 트리.
- 모든 노드를 연결하는 최소 간선, 최소 가중치의 합을 갖는 트리를 일컫는다.
- 사용 사례 : 통신망 연결, 섬과 섬 사이 다리 연결 등
구현 (세부 내용은 별도의 글로 다루기로)
Kruskal 알고리즘
탐욕법을 이용한 최소 비용을 구하는 알고리즘
① 간선들을 가중치의 오름차순으로 정렬
② 정렬된 간선들을 하나씩 선택하되 사이클을 형성하지 않는 간선만 선택
③ 해당 간선을 현재 MST 집합에 추가
Prim 알고리즘
시작 노드에서부터 출발해 신장트리 집합을 단계적으로 확장해 나가는 방법
① 시작 노드를 MST 집합에 포함
② 앞 단계에서 만들어진 MST 집합에 인접한 노드들 중 최소 간선으로 연결된 노드를 선택해 트리 확장
③ 위 과정을 트리가 (노드 개수 - 1) 개의 간선을 가질 때까지 반복
YOU ARE BREATHTAKING