오늘은 최소신장 트리와 알고리즘에 대해 수강하였다.
최소 신장 트리란?
신장트리란 그래프 내 모든정점을 포함하는 최소연결부분 그래프이다. 최소한의 간선으로 모두 연결된 그래프라고 생각하면 된다. 최소신장트리는 최소한의 간선으로 모든정점이 연결되어있어야 하고, 모든 신장 트리 중 가중치값이 최소이며 사이클이 발생해서는 안된다.
크루스칼 알고리즘은 그리디 개념으로 구현할 수 있고, 모든 그래프를 부분 집합으로 분리한다.
가장 가중치가 낮은 간선을 선택하고 부분 집합을 연결한다.
Union-Find 알고리즘을 통해 사이클을 방지할 수 있다.
Union-Find 알고리즘 이란 서로 다른 두 집합을 합쳐주는 Union이라는 로직과 집합의 원소가 어떤 집합에 속해있는지
판단하는 Find로직을 통해 판단해주는 데이터셋이라고 할 수 있다.
Union 연산의 예시는 아래와 같다.
초기에는 자기 자신을 부모 정점으로 설정하고, 특정 정점이 시작 정점에 속할 경우 간선의 방향을 부모정점으로 옮긴다.
아래에는 B가 A의 속할 경우로 표기 된걸 볼 수 있다.
D가 B에 속할경우 B의 부모정점인 A를 D의 부모로 설정한다.
집합의 최상위 요소를 부모로 설정한다는 뜻이다.
위와 같은 방법으로 계속 진행 해 나가다보면 집합이 완성되지만, 각원소가 어떤 집합에 속해있는지 알 수 없다.
Find 연산은 아래와 같이 동작한다.
'알고리즘 > 알고리즘' 카테고리의 다른 글
| 알고리즘 강의 18일차 - 최단 경로 알고리즘 (0) | 2023.03.29 |
|---|---|
| 알고리즘 강의 17일차 - 재귀함수 (0) | 2023.03.28 |
| 알고리즘 강의 16일차 - 소수 알고리즘 (0) | 2023.03.24 |
| 알고리즘 강의 15일차 - 그리디 기초 (0) | 2023.03.23 |
| 알고리즘 강의 14일차 - BFS, DFS (0) | 2023.03.22 |