-
최소 신장 트리 (MST : Minimum Spanning Trees)
비방향 연결 그래프를 대상으로 한다.
--> 연결 그래프 : 모든 정점 간의 경로가 존재하는 그래프이다
그래프의 신장 트리(spanning tree)
- 그래프의 정점 집합인 V와 간선 집합의 개수는 |V| - 1 개 이다.
- 싸이클이 없어야 한다.
그래프의 최소 신장 트리 활용
어떻게 하면 도로를 최소한으로 만들수 있는가?
최소 신장 트리 문제를 푸는 탐욕적 알고리즘
- 탐욕적 기준에 따라 싸이클이 생기지 않도록 연결 그래프가 되도록 간선 추가
- 최소 거리를 만족하는 최소 신장 트리는 유일하지 않을 수 있다.
- 크루스칼 알고리즘
- 탐욕적으로 간선을 추가하는 방식
- 저밀도 그래프에서 유용하다
- 프림 알고리즘
- 탐욕적으로 정점을 추가하는 방식
- 고밀도 그래프에서 유용하다.
- 다익스트라와 비슷하다
크루스칼 알고리즘
싸이클을 만들지 않는 범위에서 최소비용 간선을 하나씩 추가한다.
어떻게 싸이클을 탐지하는 것인가?
- 새로운 간선 : A - B
- A 에서 시작하여 DFS를 실행하여 B에 도달 가능하면 싸이클로 판단한다.
- Union-Find 자료구조를 사용하여 A와 B가 같은 집합에 속하면 싸이클이라고 판단한다.
Union-Find 자료구조(API)
서로소 집합의 데이터 구조의 ADT이다.
- 데이터 객체 : 전체지합의 원소들과 그 원소들의 서로소 집합
- find() 연산 : 집합의 대표 원소 찾기
- union() 연산 : 두 개의 서로소 집합의 합집합 구하기
역트리를 사용하여 서로소 집합을 표현
1번의 집합을 2번과 3번으로 만들면 싸이클 판별할 수 있다.
이 중에서 가장 좋은 그림은 바로 2번이다.
2, 3번 둘다 싸이클을 판단할 수 있다. 하지만 2번의 깊이가 3번보다 낮다. 그래서 빨리 끝날 수 있다.
- 역트리 : 자식이 아닌 부모노드를 가리키는 트리
- 트리의 구현 : 부모 배열 parent[], 깊이 배열 depth[]
- parent[i] = i, depth[i] = 0 으로 초기화한다.
- find 연산 : 원소가 속한 노드의 루트 노드 찾기
- union 연산 : 두 개의 루트를 합집합로 만들기
크루스칼 알고리즘
Union-Find 데이터구조를 사용하는 알고리즘이다.
간선을 추가함으로써 싸이클이 생성되는지를 판단한다.
- 간선 <a , b> 인 경우 find(a) = find(b)이면, 싸이클이라고 판단한다.
주의할 점
최소신장트리에 포함되는 간선의 집합 구현
우선 큐로 구현한다.(우선 순위는 간선의 가중치가 작은 것)
정렬
힙
최단 경로 문제
가중치를 갖는 방향 그래프를 대상으로 한다.
종류
- 모든 정점에서 다른 모든 정점에 이르는 최단 경로 문제 : 플로이드 알고리즘
- 단일 출발점에서 모든 정점까지의 최단 경로 문제 : 다익스트라 알고리즘
- 단일 출발점에서 단일 도착점까지의 최단 경로 문제
가중치에 따른 문제의 종류
- 가중치가 모두 양수 : 다익스트라 알고리즘
- 음의 가중치 허용 : 벨만-포드(Bellman-Ford) 알고리즘
다익스트라 알고리즘
- 단일 출발점 최단 경로 문제
- 시작 정점 -> 모든 정점의 최단 경로 트리(SPT)를 생성한다.
- 우선순위 큐를 사용한다.
- 우선순위의 키는 정점, 우선순위는 정점까지의 현재 최단 거리
- 2개의 보조 배열 distTo[]와 edgeTo[] 사용 : 결과 저장
- distTo[v] : s로부터 v로 가는 최단 경로의 길이
- edgeTo[v] : s로부터 v로 가는 최단 경로에서 직전 정점