728x90 Kruskal algorithm1 크루스칼 알고리즘(Kruskal algorithm) 크루스칼 알고리즘에 대해 배워보겠습니다. 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다. 그니깐 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이죠. 실제로 여러 개의 도시 연결을 위해 도로 건설 최소 비용을 위해 적용되는 알고리즘 입니다. 그래프 용어를 정리해 보겠습니다. 노드 = 정점 = node = 도시 : 그래프에서 동그라미 간선 = 거리 = edge = 비용 : 그래프에서 선 이 그림의 노드 개수는 7개이고 간선의 개수는 11개입니다. 즉 7개의 도시, 11개의 도로인거죠. 크루스칼 알고리즘의 핵심은 다음과 같습니다. 정렬 후 비용이 작은 ( 거리가 짧은) 순서대로 그래프에 포함시키자. 모든 노드를 최소 비용 연결시키는 게 목적이니 모든 노드를 오.. 2020. 6. 4. 이전 1 다음 728x90
