최소 비용 신장 트리
그래프의 신장 트리 중, 간선의 가중치의 총합이 가장 작은 신장 트리
Prim's Algorithm
현재 신장 트리에서 최소 가중치로 진출하는 미방문 정점 탐색
- 구현
- 시작 정점 하나로 구성되는 최초 부분 신장 트리를 만든다
- 현재 단계 부분 신장 트리에서 최소 가중치로 방문 가능한 미방문 정점
별도 변수 저장을 찾 아 부분 신장 트리에 추가정렬 또는 우선순위 큐 사용- 모든 정점이 부분 신장 트리에 포함될 떄 까지 위 과정 반복
- 단순 구현시 O(V^2) , 우선 순위 큐 사용시 (O(V+E)log V)
Kruskal's Algorithm
간선 정렬 및 서로소 집합 구조 활용
- 구현
- 그래프의 간선들을 가중치의 오름 차순으로 정렬한다.
- 정렬된 간선 리스트
우선순위 큐에서 최소 가중치이며, 사이클을 형상하지 않는서로소 집합 구조간선과 정점을 부분 신장 트리에 추가
- O(E log E)
Boruvka's Alogrithm
그래프 축약 활용, 병렬 프로그래밍에서 효과적
- 구현
- 주어진 그래프의 모든 정점에 대해 정점별 최소 가중치 진출 간석을 찾아 연결하여 포레스트를 만든다.
그래프 축약- 포레스트를 구성하는 트리들 사이에 순환이 발생하지 않고, 최소 가중치로 연결되는 간선을 찾아 연결한다.
- 포레스트가 하나의 트리로 연결될 때 까지 위 과정을 반복한다.
- O(E log V)
GameProgrammer