kruskal's algorithm (1) 썸네일형 리스트형 126. Kruskal's Algorithm 크루스칼 알고리즘(Kruskal's Algorithm)은 무향 그래프의 최소 스패닝 트리를 구하는 알고리즘 중 하나로, 다음과 같은 방법으로 작동한다. 1. 확인하지 않은 간선들 중 가중치가 가장 작은 간선 하나를 고른다. 2. 현재까지의 최소 스패닝 트리에서 선택한 간선이 연결하는 두 정점이 연결되어 있지 않다면, 이 간선을 최소 스패닝 트리에 추가한다. 3. 모든 간선을 확인했다면 종료한다. 그렇지 않다면 1번으로 돌아간다. 설명이 매우 간단하게 끝난다. 예시를 통해서 자세히 살펴보자. 앞에서 나온 그래프이다. 여기서 가중치가 작은 간선들부터 하나씩 확인하면서 최소 스패닝 트리를 만든다. 먼저 가중치가 $2$인 간선들이 최소 스패닝 트리에 추가된다. 다음으로 가중치가 $3$인 간선을 확인하는데, 정점.. 이전 1 다음
