Computer Science/알고리즘1 Kruskal 알고리즘 네트워크의 모든 정점을 최소 비용으로 연결하는 해답을 구하는 것 탐욕적인 방법으로 매 순간 가장 최적의 비용인 노드를 선택하는데 동작 방법은 다음과 같다 1. 간선들의 비용을 오름차순으로 정렬한다 2. 최소 비용부터 하나씩 선택하는데 사이클을 형성하는 간선을 제외 3. 해당 간선을 현재 MST에 추가한다 사이클 생성 여부 union-find 알고리즘 사용 시간복잡도 간선들을 정렬하는데 시간복잡도가 결정된다 퀵정렬을 사용하면 O(elog2e) 희소 그래프인 경우 Kruskal알고리즘이 적합 밀집그래프인 경우 Prim이 적합 Union-Find public int Find(int n){ if(n == Parent[n]) return n; else return Parent[n] = Find(Parent[n]).. 2021. 4. 12. 이전 1 다음