기본 콘텐츠로 건너뛰기

개발 공부 - [그래프 알고리즘] 순회 - 최소비용신장트리(minimum spanning tree) - 2

 Kruskal의 알고리즘


에지들을 가중치의 오름차순으로 정렬한다.

에지들을 그 순서대로 하나씩 선택해간다.

단, 이미 선택된 에지들과 사이클(cycle)을 형성하면 선택하지 않는다.

n-1개의 에지가 선택되면 종료한다.


: 구현이 간단하지는 않다고 한다. 

이것은 java 소스를 참조하겠음...



Kruskal 알고리즘이란

탐욕적인 방법(greedy method) 을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것


탐욕적인 방법

결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 것

탐욕적인 방법은 그 순간에는 최적이지만, 전체적인 관점에서 최적이라는 보장이 없기 때문에 반드시 검증해야 한다.

다행히 Kruskal 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다.

MST(최소 비용 신장 트리) 가 1) 최소 비용의 간선으로 구성됨 2) 사이클을 포함하지 않음 의 조건에 근거하여 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택 한다.


참조 : https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html




왜 MST가 찾아지는가?

Kruskal의 알고리즘의 임의의 한 단계를 생각해 보면,

현재까지 알고리즘이 선택한 에지의 집합 :A

A를 포함하는 MST가 존재한다고 가정할 때, 

지난번 참조: 

A가 어떤 MST의 부분집합이고, (S,V-S)는 A를 존중하는 컷이라고 하자,

이 컷을 cross하는 에지들 중 가장 가중치가 작은 에지 (u,v)는 A에 대해서 안전하다.

 

사이클 검사

초기 상태 : 선택된 에지 없음

각각의 연결요소를 하나의 집합으로 표현하여 

사이클이 생기는지, 생기지 않는지 검사하는 것이 중요하다.

모든 노드들을 집합으로 만들어서, 

다음 간선을 이미 선택된 간선들의 집합에 추가할 때 사이클을 생성하는지를 체크한다.

새로운 간선이 이미 다른 경로에 의해 연결되어 있는 정점들을 연결할 때 사이클이 형성된다.

즉, 추가할 새로운 간선의 양끝 정점이 같은 집합에 속해 있으면 사이클이 형성된다.

사이클 생성 여부를 확인하는 방법은 추가하고자 하는 간선의 양끝 정점이 같은 집합에 속해 있는지를 먼저 검사해야 한다.


이거는 그래서 각각의 노드들을 유일한 원소로 가지는 집합을 만들어서 초기화를 하고, 

반복 : 노드 v가 속한 집합을 찾고, u와 v가 속한 두 집합을 하나로 합치는 것이다.

이런 식으로 n-1번 반복하는 식으로 알고리즘을 짜면 된다고 한다.



댓글

이 블로그의 인기 게시물

Ebook - 전자책 drm 상관 없이 pdf로 만들기

yes24와 교보문고에서 ebook을 구매 해야 했는데 너무 불편하고, 필기가 매우 화날 정도로 안 좋아서 원시적으로 사용하기로 했다. 1. 목적 : ebook에서 필기 및 사용이 불편하여 pdf로 변환  2. 용도 : 개인 사용 목적이며 화질이 다소 저하되어도 필기만 용이하면 상관 없음 3. 방법 1) 휴대폰 및 카메라로 동영상을 촬영했다. DRM 때문에 프로그램으로는 촬영이 안 되는 것을 확인했다. (사실 개인 사용 목적이면 기본 화면 캡쳐를 사용해도 된다...) 2) 마우스 클릭 해주는 매크로를 사용했다. (1) key_macro.exe > https://blog.daum.net/pg365/250 듀얼 모니터에서 위치 이탈 현상이 있긴 해도 괜찮았다. (2) AutoClick.exe > http://bestsoftwarecenter.blogspot.com/2011/02/autoclick-22.html 이 걸로 잘 사용했다. 3초마다 한 번 클릭하도록 사용했다. 3) 동영상을 이미지로 변경해주는 프로그램을 사용했다. Free Video to JPG Converter > https://www.dvdvideosoft.com/products/dvd/Free-Video-to-JPG-Converter.htm (240826: 다운로드 시 정상적으로 되지 않아서 URL 수정) 일 하면서 듀얼 모니터에 켜 놨는데 속도가 괜찮았다. * Every frame 으로 사용해야 한다. 4) 중복 사진 제거해주는 프로그램을 사용했다. VlsiPics  > http://www.visipics.info/index.php?title=Main_Page 생각보다 느리니 퇴근시에 걸어놓고 가면 된다. 한번 play가 끝나면 Auto-select 하고 Delete 하면 된다. 5) 이미지를 일괄 Crop 작업 해주는 프로그램을 사용했다. JPEGCrops > https://jpegcrops.softonic.kr/ *...

개발 공부 - PC 카카오톡 작업 표시줄 아이콘 이미지 변경 방법

PC 카카오톡 사용시 작업 표시줄에서 아이콘 이미지를 변경하는 방법이다. 1) 작업 표시줄 내 카카오톡 아이콘에서 마우스 오른쪽 버튼을 누른  뒤 속성에 들어간다. 2) 아이콘 변경에서  C:\Windows\system32\imageres.dll C:\Windows\system32\shell32.dll C:\Windows\system32\DDORes.dll C:\Windows\System32\moricons.dll (MS DOS Icons) 등을 누른 뒤 적당한 것을 선택하여 적용한다. * 사내 메신저 아이콘을 참고해도 된다. 참고 : 기본 아이콘 위치 https://blog.silnex.kr/windowstip-windows-%EA%B8%B0%EB%B3%B8-%EC%95%84%EC%9D%B4%EC%BD%98-%EC%9C%84%EC%B9%98/ 2022. 11. 29.  생각보다 유입이 많아서 놀랐습니다. PC 카톡 사용자 화이팅!

운동 정보 - 어메이즈핏 밴드 5 스마트밴드 나이키 런 클럽(NRC = Nike Run Club) 연동

 나이키 런 클럽 쓰려고 산 어메이즈핏 밴드5 인데 연동이 영 어려워서 찾아보고 써봤다. 1. Zepp 앱은 연동이 되어 있어야 한다. 2.  Zepp 앱 -> 프로필 -> 내 기기 -> Amazfit Band 5 3. 검색 가능 : 켜짐 활동 심박수 공유 : 켜짐 연결 제한 : 꺼짐 (기본) 백그라운드에서 실행 : 제외로 등록 4. NRC(나이키 런 클럽) 앱 -> 설정 -> 러닝 설정 -> 기기 5. 심박수 표시 -> 블루투스에서 AmazFit Band 5 누르고 NRC 즐기면 된다! * 안드로이드 이용자입니다.