[JS] 크루스칼(Kruskal) 알고리즘

1. 가중치 그래프 가중치 그래프는 간선에 가중치를 할당한 그래프를 말한다. 가중치 그래프에서 간선에 주어진 가중치는 비용, 거리, 시간을 의미하는 값이 될 수 있다. 크루스칼(Kruskal) 알고리즘은 비용, 거리, 시간을 최소화하는 신장트리를 만들기 위해 나온 알고리즘이다. 즉, 모든 가중치의 합이 최소 값이 되어야 한다는 것이다. 최소 값이 나오게 하려면, 가중치를 오름차순으로 n-1만큼 더하면 된다. 그런데 앞에서 크루스칼 알고리즘에 대해 설명할 때 신장트리라는 말을 한 적이 있다. 신장 트리란, n 개의 정점을 가진 그래프 G에서 모든 정점이 n-1개의 간선으로 이루어진 트리를 말한다. 2. 크루스칼(Kruskal) 알고리즘 크루스칼 알고리즘은 두 가지 방법이 있다. 첫 번째 방법은 가중치가 높..

2020.06.25