728x90
728x90
MST(Minimum Spanning Tree 최소 신장 트리)
신장 트리 : 모든 정점이 연결된 그래프, 사이클이 존재하지 않아야 한다.
- n개의 점을 (n-1) 개의 간선으로 연결한다.
최소 신장 트리 : 신장 트리 중 간선 가중치의 합이 가장 작은 신장 트리를 의미한다.
Prim(프림) 알고리즘
시작 정점에서 출발하여 신장트리 집합을 단계적으로 확장해 나가는 방법이다.
수행 과정
- 임의의 정점을 시작 지점으로 선택
- 연결된 모든 간선의 가중치를 비교
- 가장 작은 무게의 간선 선택(사이클이 만들어지지 않도록)
- 모든 정점이 연결될 때까지 2~3번 과정 반복
시간복잡도
V : 정점의 개수
E : 간선의 개수
- 우선순위 큐로 구현
- 우선순위 큐 생성 작업 : O(logV) * O(E) = O(ElogV)
- 각 노드에서 인접 간선을 찾는 작업 : O(V의 차수) = O(2E) = O(E)
- 힙에 삽입 : O(logV)
- 총 탐색 작업 : O(VlogV)
- 모든 노드 탐색 : O(V)
- 노드에서 최소 간선 탐색 : O(logV)
- 총 시간복잡도 : O(ElogV + VlogV) = O(ElogV)
- 보통 E가 V보다 크기 때문에 O(ElogV) 라고 할 수 있다.
- 우선순위 큐 생성 작업 : O(logV) * O(E) = O(ElogV)
- 배열로 구현 : O(V^2)
- 피보나치 힙으로 구현 : O(E+VlogV)
Kruskal(크루스칼) 알고리즘
탐욕적인 방법(greedy method) 을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것
수행 과정
- 모든 간선을 무게 순으로 정렬
- 가장 작은 가중치의 간선 선택(사이클이 만들어지지 않도록)
- 모든 정점이 연결될 때까지 2번째 과정 반복
시간복잡도
- 간선 정렬 : O(ElogE) E : 간선의 개수
- find 작업 : 정점이 속한 집합을 반환한다. - O(1)
- union 작업 : 두 집합을 합친다 - O(1)
- 총 시간복잡도 : O(ElogE)
728x90
728x90
'Computer Science > Algorithm' 카테고리의 다른 글
암호화 알고리즘 (1) | 2023.03.09 |
---|---|
재귀함수(Recursion) (0) | 2023.03.09 |
그리디 알고리즘(Greedy Algorithm) & 동적 계획법(Dynamic Programming) (0) | 2023.03.09 |
Binary Search(이진탐색) (2) | 2023.03.09 |