Algorithm/Study
2021. 9. 24.
그래프 이론 : 크루스칼 알고리즘
크루스칼 알고리즘 PRE. 신장 트리 : 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 크루스칼 알고리즘 개념 : 최소한의 비용으로 신장 트리를 찾을 때 사용하는 대표적인 최소 신장 트리 알고리즘 : N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우 - 그리디 알고리즘, 서로소 판별 알고리즘(사이클) - 최종적으로 신장 트리에 포함되는 간선 개수 = 노드 개수 - 1 - 항상 최적의 해 - 시간 복잡도 : O(ElogE) (E : 간선 개수) // 간선 정렬 작업. 서로소집합 알고리즘은 정렬 알고리즘 보다 시간복잡도 작음. - 과정 1) 모든 간선에 대하여 간선 데이터를 비용에 따라 오름차순으로 정렬..
