algorithm/알고리즘
크루스칼 알고리즘 (Kruskal Algorithm)
su0a
2024. 3. 4. 23:58
크루스칼 알고리즘을 이해하기 위한 필수 개념
1. 신장 트리 : 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 없는 부분 그래프를 의미한다.
2. 최소 신장 트리 : 신장 트리 중에서 최소한의 비용으로 구현된 신장트리를 의미한다.
크루스칼 알고리즘은 최소 신장 트리 알고리즘이며 그리디 알고리즘으로 구현된다 !
크루스칼 알고리즘의 동작 과정
1. 간선 데이터를 비용에 따라 오름차순 정렬한다.
2. 모든 간선을 한번씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
- 사이클 발생하지 않는 경우 => 최소신장트리에 추가한다.
- 사이클 발생하는 경우 => 최소신장 트리에 추가시키지 않는다.
1. 간선 데이터를 비용에 따라 오름차순 정렬
| 간선 | ( 3 , 5 ) | ( 4 , 5 ) | ( 1 , 3 ) | ( 1 , 5 ) | ( 3 , 4 ) | ( 1 , 2 ) | ( 2 , 3 ) |
| 비용 | 10 | 20 | 30 | 40 | 50 | 60 | 70 |
2. 비용이 최소인 간선부터 확인하며 사이클을 만드는지 확인
크루스칼 알고리즘을 이용한 문제풀이 및 코드