크래프톤 정글 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번 과정을 반복

1. 맨 처음에는 모든 정점이 서로 다른 그룹에 속해 있는 상태로 시작한다.

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

3. 두 정점은 그룹 색이 다르기 때문에 같은 그룹으로 만든다.

 

 

4. 제일 낮은 비용의 간선을 선택해서 같은 그룹으로 만들어준다.

 

 

5. 다음으로 비용이 작은 간선을 선택한다.

6. 정점이 5개인데 4개의 간선을 최소 신장 트리에 추가 → 최소 신장 트리 완성!

 

 

Union Find

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

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

 

 

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