문서 보기문서 편집수정 내역 크루스칼 알고리즘 (덤프버전으로 되돌리기) [include(틀:토막글)] [목차] == 개요 == 최소 비용 신장 [[트리(그래프)|트리]]를 [math(O(ElogV))]만에 구하는 [[알고리즘]]이다. == 구현방법 == * 그래프의 모든 간선의 집합 [math(E)]을 만든다. * [math(E)]가 비어있지 않을 때까지 * [math(E)]의 간선들 중 가중치가 최소인 간선을 지운다.[* [[정렬 알고리즘|정렬]]해도 된다.] * 삭제된 간선이 가리키는 정점 [math(x, y)]를 연결하여도 사이클이 발생하지 않는다면[* 이 과정을 [[Union Find]]으로 수행할 수 있다.] 연결한다. [[분류:알고리즘]]캡챠되돌리기