https://sinclairstudio.tistory.com/24
union-find 알고리즘을 알아보자! in Python
1. 그래프 자료구조 union-find 알고리즘은 그래프 자료구조형에서 적용된다. 그래프의 구현방법은 2가지 방식이 존재한다 1) 인접행렬 (Adjacency Matrix) : 2차원 배열을 사용하는 방식 공간복잡도: 노
sinclairstudio.tistory.com
Union find 정리 글은 위에 !! 이건 서로소 집합인지 판별하고 합집합 연산을 수행하는 알고리즘이다
크루스칼 알고리즘은 무엇인가 !!
우리가 그래프 알고리즘에서, 최저비용 경로를 계산할 때 사용할 수 있다
다익스트라는 최단거리 ! 크루스칼은 최저비용 !
1. 신장트리
하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다
루트노드가 같다면 사이클이 발생한다
2. 크루스칼 알고리즘
크루스칼 알고리즘은 신장 트리들 중에서 최소비용으로 만들 수 있는 신장 트리를 찾는다 즉, 가장 적은 비용으로 모든 노드들을 연결 할 수 있다.
크루스칼 알고리즘은 그리디 알고리즘으로 분류된다. 모든 간선의 비용에 대해 정렬을 (오름차순) 수행한 후에 , 가장 비용이 작은 간선부터 집합에 포함시킨다. 그리고 사이클을 발생시키는 간선의 경우에는 집합에 포함시키지 않는다.
사이클을 판별할 때 union-find 알고리즘에서 등장한, find_parent() 함수를 통해 루트 노드를 찾아서 각각의 루트 노드가 다른지 확인해야 한다. 루트 노드가 같으면 사이클이 발생하며, 다르면 사이클이 발생하지 않는 경우이다.
예를 들어 다음과 같은 그래프가 있다고 가정하자.
간선의 비용을 오름차순으로 정렬하면 다음과 같다.
| 간선 | (3, 4) | (1, 2) | (4, 5) | (3, 5) | (2, 5) | (1, 5) | (2, 3) |
| 비용 | 7 | 9 | 13 | 15 | 17 | 20 | 30 |
정렬된 간선중 가장 작은 비용 7을 가지는 간선 (3, 4)를 집합에 포함시킨다.
| 간선 | (3, 4) | (1, 2) | (4, 5) | (3, 5) | (2, 5) | (1, 5) | (2, 3) |
| 비용 | 7 | 9 | 13 | 15 | 17 | 20 | 30 |
그다음으로 작은 비용인 9를 가지는 간선 (1, 2)를 집합에 포함한다.
| 간선 | (3, 4) | (1, 2) | (4, 5) | (3, 5) | (2, 5) | (1, 5) | (2, 3) |
| 비용 | 7 | 9 | 13 | 15 | 17 | 20 | 30 |
그다음으로 작은 비용인 13를 가지는 간선 (4, 5)를 집합에 포함한다.
| 간선 | (3, 4) | (1, 2) | (4, 5) | (3, 5) | (2, 5) | (1, 5) | (2, 3) |
| 비용 | 7 | 9 | 13 | 15 | 17 | 20 | 30 |
그다음으로 작은 비용은 15이지만 edge(3,5)를 집합에 포함시킬 경우, cycle을 생성하므로 이는 포함시키지 않는다.
| 간선 | (3, 4) | (1, 2) | (4, 5) | (2, 5) | (1, 5) | (2, 3) | |
| 비용 | 7 | 9 | 13 | 17 | 20 | 30 |
node의 개수 5개 edge의 개수 4개로 모든 노드를 잇는 신장트리가 완성되었다!! 최소비용은 7 + 9 + 13 + 17 = 46 이다.
| 간선 | (3, 4) | (1, 2) | (4, 5) | (2, 5) | (1, 5) | (2, 3) | |
| 비용 | 7 | 9 | 13 | 17 | 20 | 30 |
