Kruskal's Algorithm 썸네일형 리스트형 11. 최소 신장 트리(MST): 크루스칼 알고리즘(Kruskal's Algorithm) 최소 신장 트리 혹은 최소 스패닝 트리라고 불리는 MST(Minimum Spanning Tree)는 가중치가 포함된 무향의 그래프가 주어졌을 때, 모든 노드들이 포함되면서 비용은 최소가 되는 부분 그래프인 트리를 의미합니다. 이와 같은 조건을 만족하는 MST를 찾기위해 크루스칼 알고리즘(Kruskal's Algorithm)이나 프림 알고리즘(Prim's algorithm)을 사용합니다. 이 두가지 알고리즘은 동일한 시간복잡도를 갖고 있기 때문에 어느 알고리즘이 더 우월하다고 할 수 없으나, 크루스칼 알고리즘은 간선을 기준으로 구현되고, 프림 알고리즘은 노드 기준으로 알고리즘이 구현된다는 부분에서 차이를 갖고 있습니다. 이번에는 간선을 기준으로 한 크루스칼 알고리즘을 설명해보도록 하겠습니다. 크루스칼 알고.. 이전 1 다음