prim vs kruskal vs Dijkstra 프림 크루스칼 다익스트라

    
 Prim 알고리즘과 Kruskal 알고리즘은 둘 다 최소 신장 트리(MST, Minimum Spanning Tree)를 구하는 대표적인 알고리즘입니다. 그러나 이 두 알고리즘은 작동 방식에서 차이가 있습니다. 아래에서 차이점을 설명하겠습니다.

### 1. 작동 방식
- **Prim 알고리즘**:  
  - Prim 알고리즘은 그래프에서 임의의 정점을 선택하고, 해당 정점에서 시작하여 인접한 정점으로 확장하는 방식으로 최소 신장 트리를 만들어 갑니다. 
  - 이미 선택된 정점들로부터 가장 가중치가 작은 간선을 선택해서 새로운 정점을 포함시킵니다. 
  - 이 과정은 모든 정점이 포함될 때까지 반복됩니다.
  
- **Kruskal 알고리즘**:  
  - Kruskal 알고리즘은 그래프의 모든 간선을 가중치 순서대로 정렬한 다음, 가중치가 가장 작은 간선부터 선택하면서 최소 신장 트리를 구성합니다. 
  - 이때 사이클이 생기지 않도록 간선을 선택하며, 사이클이 발생하면 그 간선은 버려집니다. 
  - 간선 중심적 알고리즘으로, 간선을 하나씩 추가하는 방식입니다.

### 2. 자료 구조
- **Prim 알고리즘**:  
  - 주로 **힙(Heap)** 자료구조를 사용하여 가장 작은 가중치의 간선을 효율적으로 선택합니다.
  - 인접 리스트나 인접 행렬을 활용하여 인접한 정점을 관리하는 경우가 많습니다.
  
- **Kruskal 알고리즘**:  
  - **분리 집합(Disjoint Set)** 자료구조, 즉 유니온-파인드(Union-Find)를 사용하여 사이클이 생기는지 여부를 관리합니다.
  - 간선 리스트가 정렬된 형태로 관리됩니다.

### 3. 시간 복잡도
- **Prim 알고리즘**:  
  - 힙을 사용하는 경우 \(O(E \log V)\)입니다. 여기서 \(E\)는 간선의 수, \(V\)는 정점의 수입니다.
  - 전체 간선을 다 확인하는 Kruskal 알고리즘에 비해 상대적으로 더 적은 간선만 확인하는 경우 빠를 수 있습니다.

- **Kruskal 알고리즘**:  
  - 간선 정렬이 필요하므로 \(O(E \log E)\)의 시간이 소요됩니다. 
  - 또한, 유니온-파인드 연산이 효율적이라 전체 시간 복잡도는 \(O(E \log V)\)입니다.

### 4. 적용하는 상황
- **Prim 알고리즘**:  
  - 밀집 그래프에서 효과적입니다. 정점 간의 간선이 많은 경우, Prim 알고리즘이 더 빠르게 작동할 수 있습니다.
  
- **Kruskal 알고리즘**:  
  - 희소 그래프에서 효과적입니다. 간선의 수가 적은 경우 Kruskal 알고리즘이 더 유리할 수 있습니다.

### 요약
- **Prim 알고리즘**: 정점 중심, 하나의 정점에서 시작해서 점차 확장해 나가는 방식.
- **Kruskal 알고리즘**: 간선 중심, 가장 가중치가 작은 간선부터 선택해 나가는 방식.

두 알고리즘은 상황에 따라 서로 다른 성능을 보이며, 특정 그래프 구조에서 더 효율적일 수 있습니다.


### Kruskal 알고리즘
- **간선 중심적** 접근입니다.
- 모든 간선을 가중치 순으로 정렬한 후, 가장 작은 간선부터 선택합니다.
- **사이클이 생기지 않도록** 간선을 선택하며, 사이클이 발생하면 그 간선은 제외합니다.
- 따라서, 간선들을 하나씩 추가하며 트리를 구성해 나가고, 이 과정에서 트리 구조가 완성될 때까지 간선을 추가합니다.

### Prim 알고리즘
- **정점 중심적** 접근입니다.
- 하나의 시작 정점을 선택한 후, 그 정점에서부터 **확장**해 나가는 방식입니다.
- 이미 연결된 정점 집합에서 **가장 작은 가중치의 간선**을 선택해 새로운 정점을 연결합니다.
- 이 과정을 반복해서 트리가 점차적으로 확장되며, 모든 정점이 포함될 때까지 진행됩니다.
- 연결된 부분을 **덩어리**로 생각하고, 이 덩어리에서 바깥으로 뻗어가는 가장 작은 간선을 선택하는 방식입니다.

Kruskal은 간선 중심, Prim은 정점 중심의 확장 방식을 취하며, 각각 사이클 생성을 방지하거나 연결된 덩어리에서 확장하는 점이 큰 차이입니다.

다익스트라(Dijkstra) 알고리즘은 그래프에서 **한 정점에서 다른 모든 정점까지의 최단 경로**를 찾는 알고리즘입니다. 주로 **가중치가 있는 그래프**에서 사용되며, 음의 가중치를 가지지 않는 그래프에서만 사용할 수 있습니다. 다익스트라 알고리즘은 네트워크 경로 찾기나 최단 경로 문제를 해결하는데 널리 쓰입니다.

### 다익스트라 알고리즘의 핵심 개념

1. **출발점 설정**:
   - 시작 정점을 하나 선택합니다. 이 정점으로부터 다른 정점들까지의 최단 거리를 찾습니다.

2. **최단 경로 추정**:
   - 초기에는 출발 정점에서 자신을 제외한 모든 정점까지의 거리를 무한대(∞)로 설정하고, 출발 정점의 거리는 0으로 설정합니다.
   - 방문한 정점들로부터 인접한 정점들로 가는 경로 중에서 가장 짧은 경로를 찾습니다.
   - 우선순위 큐(보통 최소 힙)를 사용하여 현재까지 확인된 최단 거리를 기준으로 정점을 선택합니다.

3. **정점 확장**:
   - 현재까지 최단 거리가 확정된 정점에서 인접한 정점들로 가는 경로를 확인하며, 해당 경로를 통해 더 짧은 거리가 나올 수 있는지 확인합니다.
   - 만약 더 짧은 거리가 발견되면, 해당 정점까지의 거리를 업데이트합니다.
   - 이 과정을 모든 정점에 대해 반복하여, 출발 정점에서 각 정점까지의 최단 거리를 구합니다.

4. **종료 조건**:
   - 더 이상 확인할 정점이 없을 때 알고리즘이 종료됩니다.
   - 이때, 출발 정점으로부터 각 정점까지의 최단 거리가 구해집니다.

### 다익스트라 알고리즘의 특징

- **시간 복잡도**: 다익스트라 알고리즘의 시간 복잡도는 구현 방식에 따라 다릅니다. 일반적으로 우선순위 큐를 사용한 구현에서는 \(O(E \log V)\)입니다. 여기서 \(E\)는 간선의 수, \(V\)는 정점의 수입니다.
  
- **가중치가 양수인 그래프에서만 작동**: 다익스트라 알고리즘은 **음의 가중치**를 가진 간선을 처리할 수 없습니다. 음의 가중치가 있는 경우에는 벨만-포드(Bellman-Ford) 알고리즘을 사용해야 합니다.

- **그리디 알고리즘**: 다익스트라는 그리디(탐욕적) 접근 방식을 사용합니다. 즉, 매 단계에서 가장 최단 경로를 선택하여 문제를 해결합니다.

### 다익스트라 알고리즘과 Prim 알고리즘의 유사점
- 두 알고리즘 모두 그리디 알고리즘에 속합니다.
- 둘 다 우선순위 큐(힙)를 사용하여 가장 작은 값을 선택해 나가는 방식입니다.
- **차이점**은 다익스트라는 "최단 경로"를 찾는 문제를 해결하고, Prim은 "최소 신장 트리"를 찾는 문제를 해결하는 점입니다.

### 다익스트라 알고리즘의 과정 예시

1. 출발점에서부터 시작하여 각 정점까지의 최단 거리를 무한대로 설정(출발점의 거리는 0).
2. 출발점에서 인접한 정점들로 가는 경로를 확인하고, 더 짧은 경로가 있으면 갱신.
3. 최단 경로가 확정된 정점에서 다시 인접한 정점들로 확장.
4. 모든 정점의 최단 거리가 확정될 때까지 이 과정을 반복.

이 과정에서 최단 거리가 확정된 정점은 더 이상 변경되지 않으므로, 최종적으로 출발점에서 각 정점까지의 최단 경로를 얻을 수 있습니다.