📂 알고리즘/최소신장트리

PRIM 알고리즘

최소신장트리를 만드는 두 번째 방법인 PRIM 알고리즘에 대해서 알아보자. (첫 번째 방법으로는 KRUSKAL 알고리즘이 있었다.) 1. PRIM 알고리즘 👓 1. 기본 개념 그리디 방식을 이용하여 최소 신장 트리를 찾는 방식 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 만들어 나가는 방식 2. 동작 방식 그래프에서 하나의 정점을 선택하여 트리를 만든다. 트리와 연결되어 있지만 아직 선택되지 않은 정점들 중에서 간선의 가중치가 가장 낮은 정점을 트리에 포함시킨다. 트리가 N-1의 간선을 가질 때까지 2번을 반복한다. 2. 구현 (JAVA) 🤿 구현 방식으로는 아래의 2가지 방법이 있다. 반복문을 통해 다음 정점을 찾는 방식 PriorityQueue를 이용해 다음 정점을 찾는 방식 위의 예시를 통..

KRUSKAL 알고리즘

1. 기본 개념 🧪 1. 신장 트리 (Spanning Tree) n개의 정점을 가지는 그래프에서 n개의 정점을 모두 연결할 수 있는 n-1개의 간선으로 이루어진 트리 (간선은 n-1개 이상일 수 있다.) 물론 n-1개 이상의 간선을 가져도 신장 트리가 될 수 있다. 2. 최소 신장 트리(Minimum Spanning Tree) 무향 가중치 그래프에서 가중치의 합이 가장 작은 신장 트리를 최소 신장 트리라고 한다. 2. KRUSKAL 알고리즘 🧫 1. 기본개념 그리디 방식을 이용하여 최소 신장 트리를 찾는 방식 그리디한 방식 자체가 항상 최적의 해답을 제공한다는 보장은 없지만, KRUSKAL 알고리즘에서는 최적의 해답을 제공하는 것으로 증명되어있다. 2. 동작 방식 모든 간선들을 가중치에 따라 오름차순으로..