조합론적 최적화/Minimum spanning tree (2) 썸네일형 리스트형 절단 성질을 이용한 MST 알고리즘 증명 (Proving MST Algorithms by Cut Property) 이 포스트에서 다룰 최소 신장 트리(minimum spanning tree, MST) 문제는 매우 유명한 조합론적 최적화 문제입니다. 아마 이 글을 읽으러 들어오셨다면 아무래도 학부 자료 구조나 알고리즘 수업 시간에 이 문제가 어떤 문제인지에 대해서 들어 보셨을 것입니다. 굳이 다시 정의를 해 보자면, 이 문제는 간선마다 비용이 정의된 그래프 위에서 최소의 비용으로 모든 정점을 연결하는 트리를 찾는 문제입니다. 수업 시간에 이 문제를 다루면서 분명 이 문제를 해결하는 알고리즘에 대해서도 함께 배우셨을 것입니다. 적어도 다음 두 알고리즘은 배웠을 텐데, 바로 크루스칼의 알고리즘(Kruskal's algorithm)과 프림의 알고리즘(Prim's algorithm)입니다. 두 알고리즘 모두 한두 문장으로 설.. 보루프카 알고리즘 (Borůvka's Algorithm) 최소 신장 트리(minimum spanning tree, MST)는 최소의 비용으로 주어진 그래프의 모든 정점을 연결하는 방법으로, 학부 자료구조 수업이나 알고리즘 수업에서 이를 찾는 문제를 분명 배우셨을 겁니다. 예전에 저도 자료구조 시간에 이 문제를 배웠던 기억이 있습니다. 당시 이 문제를 푸는 방법으로 크루스칼 알고리즘(Kruskal's algorithm)과 프림 알고리즘(Prim's algorithm)을 배웠습니다. 아마 이 두 알고리즘이 가장 유명한 방법이 아닐까 싶습니다. 그런데 최근 두 알고리즘과는 또 다른 알고리즘을 알게 되었습니다. 바로, 보루프카 알고리즘(Borůvka's algorithm)인데요. 사실은 이 알고리즘이 맨 처음으로 제시된 MST 알고리즘이라고 하더군요. 찾아보니 우리말.. 이전 1 다음
