MST
최소 스패닝 트리(Minimum Spanning Tree)
Spanning Tree
그래프 내의 모든 정점을 포함하는 트리
스패닝 트리 = 신장 트리
스패닝 트리는 그래프의 최소 연결 부분 그래프이다.
- 최소연결 = 간선의 수가 가장 적다.
- n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)이고, (n-1)개의 간선으로 연결되어있으면 필연적으로 트리 형태가 되고 이것이 Spanning Tree가 된다.
Spanning Tree의 특징
DFS, BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있다.
하나의 그래프에는 많은 신장 트리가 존재할 수 있다.
스패닝 트리는 트리의 특수한 형태이므로 모든 정점들이 연결되어있어야하고 사이클을 포함해서는 안된다.
MST
Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리
최소 신장 트리
간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것을 말한다.
<그래프의 모든 정점을 연결하되, 사이클이 존재하지않도록 모든 정점을 간선으로 연결. 이 때, 간선의 가중치 합을 최소로 하며 연결>
두 그래프는 같은 그래프이지만, 서로 다른 최소 스패닝 트리를 가질 수 있다.
MST의 특징
간선의 가중치의 합이 최소여야한다.
무조건 하나의 그래프에서 하나만 생성됨을 보장하지는 않음.
사이클이 포함되어서는 안된다.
통신망, 도로망, 유통망에서 길이, 구축 비용, 전송 기간 등을 최소로 구축하려는 경우 사용됨
MST의 구현방법
탐욕적인 방법(greedy method)을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는것
- 간선 선택을 기반으로 하는 알고리즘
- 그래프의 간선들을 가중치의 오름차순으로 정렬
- 즉, 가장 낮은 가중치를 먼저 선택(사이클을 형성하지 않는)
- 해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가한다.
2.Prim MST 알고리즘
시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는방법
- 정점 선택을 기반으로 하는 알고리즘
하나의 시작점을 잡고 시작점과 연결된 정점들에 대해 가중치가 작은 간선부터 연결해 최소 스패닝 트리를 만들어 나가는 알고리즘을 의미한다.
가장 작은 간선부터 연결하되, 사이클이 생기게된다면 무시하여야한다.
최단 경로 알고리즘
- 가장 짧은 경로를 찾는 알고리즘
다익스트라 최단 경로 알고리즘 개요
- 특정한 노드에서 출발해 다른 모든 노드로 가는 최단 경로를 계산
- 음의간선이 없어야 동작
- 그리디 알고리즘으로 분류
- 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복
다익스트라 최단 경로 알고리즘 동작 과정
- 출발 노드 설정
- 최단 거리 테이블 초기화
- 방문하지않은 노드 중에서 최단거리가 가장 짧은 노드 선택
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 테이블을 갱신
- 3번과 4번 반복
다익스트라 알고리즘의 특징
- 그리디 알고리즘: 매상황에서 방문하지않은 가장 비용이 적은 노드를 선택해 임의의 과정 반복
- 한번 처리된 노드의 최단 거리는 고정
- 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는것으로 이해할 수 있다.
- 테이블에 각 노드까지의 최단 거리 정보가 저장
다익스트라 알고리즘 간단 구현 성능 분석
-
총 O(V)번에 걸쳐 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야한다.
-
전체 시간 복잡도 : O(V^2)
-
노드의 개수가 1만개를 넘어가는 문제라면?
-
다익스트라 알고리즘 동작 과정에서 최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 갖고있다.
-
처리과정에서 더짧은 경로를 찾으면 갱신
-
그래프에 있는 노드가 다 참여하고,
-
각 노드를 연결하는 그래프의 노드를 선택해서 트리를 구성할 수 있다면 신장트리
-
각각의웨이트를 합한것이 신장트리의 웨이트이다.
직접적이든 간접적이든(여러차례 엣지를 거쳐서) 모든 노드를 거치는것이 트리
- 코스를 작게해야하기때문에 최소로 비용을 낮추기 위해서 - 최소 신장 트리
우선순위 큐(Priority Queue)
- 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
별도로 우선순위를 설정하고, 차례대로 추출될 수 있다.
힙(heap)
- 우선순위 큐를 구현하기위해 사용하는 자료구조 중 하다
- 최소힙과 최대힙
- 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 사용된다.
다익스트라 알고리즘 : 개선된 구현 방법
- 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 힙 자료구조를 이용한다.
- 다익스트라 알고리즘이 동작하는 기본 원리는 동일하다.
- 현재 가장 가까운 노드를 저장해 놓기 위해 힙 자료구조를 추가적으로 이용한다.
- 현재의 최단 거리가 가장짧은노드를 선택해야하므로 최소힙 사용
- O(ElogV)
- 노드를 하나씩 꺼내 검사하는 반복문은 노드의 개수 V 이상의 횟수로는 처리되지 않는다.
- E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사하다.
이때의 비용은 4,8,7,2,1,6,2,10 이 트리에 포함된 모든 엣지를 합한것
모든 노드가 연결되기때문에 여러 신장 트리가 있을것이고, 그중에서 최소를 구하는게 최소 신장 트리
다익스트라 알고리즘(최단 경로 알고리즘)
- 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려주는 알고리즘
크루스칼 알고리즘
- 최소 비용신장 트리를 만들기위한 알고리즘
- 모든 노드가 하나로 다 연결되게, 가장 적은 비용으로
- 가중치가 최소인 간선을 하나씩 선택해 나가는 간선 기반 알고리즘
핵심개념
- 간선을 거리가 짧은 순서대로 그래프에 포함시키기
- 모든 간선 정보 오름차순
- 비용이 작은 간선부터 그래프에 포함
- 주의) 싸이클이 발생하지않도록
프림 알고리즘
- 정점을 하나 선택한 후, 정점에 연결된 간선중 가장 가중치가 작은 간선을 선택해서 연결해 나가는 정점 기반 알고리즘
- 정점을 하나씩 선택해나가기때문에 사이클은 자동으로 고려가 된다.
| 다익스트라 | 크루스칼 | |
|---|---|---|
| 구현 방법 | 우선순위 큐 + dp(점화식) | 우선순위 큐 + union find(서로소 집합) |
| 중심 | 정점 | 간선 |
| 시작점 | 출발점이 정해져있는 경우 | 간선의 가중치가 작은것부터 시작(오름차순 정렬) |
| 큐 진입시점 | dp갱신될때(최단 경로 갱신) 그 정점에서 출발하는 간선을 우선순위 큐에 추가 | 모든 정점을 우선순위 큐에 넣고 시작 |
| 용도 | 한 정점에서 다른 정점의 최단 거리를 구할때 | 최소 신장 트리를 그릴 때 |
| 최단 거리 | 임의의 두 점 간의 최단 거리 구할때 사용 | 최소의 비용(최단거리) 모든 점을 다 연결할 때 사용 |
