크래프톤 정글 6기 TIL - Day 13| 최소 신장 트리, 유니온 알고리즘

그래프 어렵다!!!

---

신장 트리

1. 모든 정점을 포함한 서브 그래프

2. 트리의 성질 : 무방향이면서 사이틀이 없는 그래프

3. 주어진 그래프의 정점이 V개일 때, 신장 트리는 V-1개

4. 주어진 그래프가 연결 그래프일때만 신장 트리가 존재

 

최소 신장 트리

주어진 방향성이 없는 그래프의 부분 그래프(Subgraph) 들 중에서 모든 정점을 포함하는 트리

 

부분 그래프 : 주어진 그래프에서 일부 정점과 간선만을 택해서 구성한 새로운 그래프

① 가운데 정점이 연결 되지 않음

②,③ 사이클 존재 → 신장 트리가 아님

④ 원래 그래프에 없던 간선 증가 → 부분 그래프 X

 

크루스칼 알고리즘

1. 간선을 크기의 오름차순으로 정렬. 제일 낮은 비용의 간선을 선택한다.

2. 현재 선택한 간선이 정점 u,v 를 연결하는 간선이라 할 때 만약 u와 v가 같은 그룹이라면 아무것도 하지 않고 넘어감. u와v가 다른 그룹이라면 같은 그룹으로 만들고 현재 선택한 간선을 최소 신장 트리에 추가

3. 최소 신장 트리에 v-1 개의 간선을 추가 시켰다면 과정을 종료. 그렇지 않다면 그 다음으로 비용이 작은 간선을 선택한 후 2번 과정을 반복

 

 

Union Find

- 그래프 알고리즘으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘

- 노드를 합치는 Union 연산과 루트 노드를 찾는 Find 연산으로 이루어짐

 

 

< 그림들 추가 예정입니다!!!>