1. Greedy Algorithm 과 크루스칼 최소 신장 트리
최소 신장 트리(Minimum Spanning Tree)는 그래프 내의 모든 정점을 최소의 비용으로 연결하는 트리이다. 최소 신장 트리를 구축하는데 한 가지 중요한 제약은 최소 신장 트리 내에 사이클이 형성되어서는 안된다는 것이다.
프림과 크루스칼 알고리즘 두 가지가 있는데, 크루스칼 알고리즘은 다음과 같이 동작 한다.
1) 그래프 내의 모든 간선의 가중치에 대한 오름차순 목록을 만든다.
2) 1)의 간선을 차례대로 순회하면서 간선을 최소 신장 트리에 추가한다. 단 추가된 간선으로 사이클리 생성되서는 안된다.
탐욕 알고리즘(Greedy Algorithm) 은 (해선택 -> 실행 가능성 검사 -> 해 검사) 가 반복되는 알고리즘이다. (Greedy Algorithm 과 거스름돈 예제 참고)
크루스칼 알고리즘은
1) 해 선택 : 가장 작은 가중치의 간선 선택
2) 실행 가능성 검사 : 사이클 형성하는지 파악
3) 해 검사: 모든 정점이 하나의 집합에 있는지 확인(모든 정점을 연결 하였는지)
이 되어 탐욕적으로 동작한다.
2. Greedy Algorithm 과 다익스트라 최단 경로
다익스트라의 최단 경로 알고리즘은 그래프 내의 한 정점에서 다른 정점으로 향하는 가장 짧은 경로를 구하는 알고리즘이다.
다익스트라 알고리즘은 다음과 같이 동작한다.
1) 각 정점 위에 시작점으로부터 자신에게 이르는 경로의 길이를 무한대로 저장한다.
2) 시작 정점의 경로 길이를 0으로 초기화 하고 최단 경로에 추가한다.
3) 최단 경로에 새로 추가된 정점의 인접 정점들에 대한 경로 길이를 갱신하고 이들을 최단 경로에 추가한다. 만약 추가하려는 인접 정점이 이미 최단 경로 안에 존재한다면 갱신되기 이전의 경로 길이가 새로운 경로의 길이보다 더 큰경우에 한해, 다른 선행 정점을 지나던 기존의 경로를 현재 정점을 경유하게 수정함
4) 그래프 내의 모든 정점이 최단 경로에 소속될 때까지 3) 을 반복함
3)은 해 선택과 실행 가능성을 검사하며, 4)가 해의 검사를 맡고 있다.
따라서 탐욕적으로 동작한다고 할 수 있다.
