C# Kruskal 알고리즘

나는 길찾기의 A* 알고리즘을 배우기 위해서 기초 단계인 MST (최소 비용 경로) 알고리즘중 하나인 Kruskal 알고리즘에 대해 배워보겠다.

 

 

 

Kruskal Algorithm

 

크루스칼 알고리즘은 현재 그래프에 존재하는 모든 그래프를 순회하면서 얼마나 적은비용으로 순회를 할수 있을지 확인할수 있는 알고리즘이다

 

크루스칼 알고리즘은 구현방법은 분리집합 OR DFS가 있는데 나는 분리 집합으로 구현을 해보겠다.

분리 집합으로 구현하기전에 분리 집합부터 설명을 하겠다.

 

분리 집합 (DisJointSet)

 

분리 집합은 서로소 집합이라고 하며 말 그대로 각각의 집합에 공통된 원소를 가지지 않는 집합이다.

 

그래서 분리 집합의 조건은 A집합과 B집합의 교집합이 아예 없다는것이 성립 되어야 가능하다.

 

분리 집합에는 Find, Union기능이 있는데

Find는 말그대로 서로 최상의 부모가(공통된 원소가 있는지) 찾는것이고

Union은 서로 이어져 있지 않다면 부모와 부모를 병합(교집합)을 하겠다는것이다.

 

 

 

 

크루스칼 알고리즘의 작동 방법은 현재 그래프에 존재하는 간선들의 가중치들을 모두 동적 배열이나 정적 배열에 담아서

오름차순으로 정렬을 하고 현재 노드들은 있는 배열 또는 해시테이블을 이용해 현재 부모는 자기 자신이라고 선언을 해놓는다.

 

이렇게 가중치가 적은 간선을 하나씩 꺼내면서 서로 최상 부모가 다르다면 두 노드중의 하나는 다른 노드의 최상부모로 바꾸고 사이클을 형성해나가면서 그 다음 적은 간선을 빼면서 최상 부모가 같다면 패스를 해주고 아니면 다시 사이클을 형성하는 방식이다.

 

 

 

 

 

 

 

 

 

 

이렇게 최상위 부모들을 연결시켜놓고 최단경로들을 찾는 Kruskal 알고리즘이였다.

 

 

 

다음 아래 링크는 최소 경로를 구하는 문제로 크루스칼을 이용해서 풀어보았다.

 

https://propim.tistory.com/54

C# 프로그래머스 LV3 섬 연결하기