크루스칼 썸네일형 리스트형 크루스칼 알고리즘 (Kruskal's Algorithm) Minimum Spanning Tree 문제를 해결하기 위해서 보통 두 가지 종류의 알고리즘 중 하나를 선택하여 사용한다. 1. 프림 알고리즘 (Prim's Algorithm) 2. 크루스칼 알고리즘 (Kruskal's Algorithm) 이 두 가지 알고리즘 모두 MST 문제에서 최적의 값을 도출할 수 있음이 이미 증명되어 있다. 이번에는 크루스칼 알고리즘에 대하여 알아보도록 하겠다. 크루스칼 알고리즘은 모든 Edge들에 대해 Weight가 작은 것부터 큰 순으로 Sorting 해놓고 Weight가 작은 Edge부터 MST에 포함시켜 나가는 방식을 사용하는데, 여기에서 핵심은 Edge를 추가했을 때 사이클 생성 여부를 체크하여 사이클이 생성되지 않는 경우 해당 Edge를 MST에 추가한다는 것이다. 모.. 더보기 이전 1 다음
