Kruskal's Algorithm (1) 썸네일형 리스트형 [Algorithm] Kruskal's Algorithm (크루스칼 알고리즘) 1. Kruskal's Algorithm 크루스칼 알고리즘은 edge를 그리디하게 선택하여 MST를 구성하는 알고리즘이다. edge를 가중치 기준으로 오름차순으로 정렬한 후 가장 작은 edge부터 순서대로 subtree에 추가하여 MST를 구성한다. 이때 해당 edge가 cycle을 이루는지 확인을 해야하는데, 이때 union-find 알고리즘은 사용하는데, 각 정점에 index를 주어서 정점들이 연결될 때마다 해당 그룹의 정점들이 모두 같은 index를 가지도록 하여 이를 비교하여 같은 index를 가지는 경우 cycle로 인식한다. 2. 크루스칼 알고리즘 구현 1) 그래프의 간선을 오름차순으로 정렬한다. 2) 가장 작은 간선을 선택하여 cycle을 그리는지 확인한다. 3) cycle을 그리는 경우는 .. 이전 1 다음