Greedy ( 탐욕적 알고리즘 )

• 여러 경우 중 하나를 선택해야 할때마다 그 순간 최적이라고 생각되는 것을 선택해 나가는 알고리즘
• 한번의 선택이 다음 선택에는 전혀 무관한 값이여야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미이다
• 적용 예가 많지 않다. >> 보통 근사치 추정에 많이 쓰인다
• TSP와 NP-complete 문제를 풀기위해 많이 쓰임

Minimum spanning tree

• 그래프에서 사용.
• 사이클 발생여부 : Union-Find 알고리즘 사용 > 사이클 테이블 만듬.

Prim algorithm

• 임의의 정점에서 가중치가 가장 작은 간선을 선택, 선택된 정점과 연결된 간선들 중 가장 가중치가 작은 것들을 선택
• 시작정점을 MST집합에 포함 > 집합에 인접한 정점들 중 최소간선으로 연결된 정점 선택하여 MST에 추가 > N-1개 간선이 될 때까지 반복

시간복잡도는 주반복문이 정점의 수n만큼 반복하고, 내부 반복문이 n만큼 반복하므로 O(n^2)

Krusckal algorithm

• 간선 선택을 기반으로함.

• 그래프의 모든 간선 중에서 가중치가 가장 작은 것부터 차례대로 선택한다 (cycle을 만드는 경우는 제외)ㅁ

• 시간복잡도는 O(nlogn)이다.

적용

• 그래프 내 적은 숫자의 간선만을 가지는 ‘희소 그래프’의 경우 Kruskal이 적합.
• 그래프에 간선이 많이 존재하는 ‘밀집 그래프’의 경우는 Prim이 적합.

Dijkstra Algorithm