크루스칼1 [Algorithm] 크루스칼 알고리즘 (Kruskal Algorithm) 크루스칼 알고리즘 (Kruskal Algorithm) 이란 그래프 내의 모든 정점들을 가장 적은 비용(cost)으로 연결하기 위해 사용되는 알고리즘이다. 그래프 내의 모든 정점을 포함하고 사이클이 없는 연결 선을 그렸을 때, 가중치의 합이 최소가 되는 상황을 구하고 싶을 때 사용한다. 즉, 최소 신장 트리(MST, Minimum Spanning Tree)를 구하기 위한 알고리즘이다. 위 그래프가 있다고 가정할 때 노드의 개수는 5개고 간선의 개수는 6개다. 크루스칼 알고리즘의 핵심은 거리가 짧은 순서대로 그래프에 포함시키는 것이다. 크루스칼 알고리즘을 자세히 다루기 전에 신장 트리와 최소 신장 트리에 대해서 다뤄보자 신장 트리 (Spanning Tree) 신장 트리 (Spanning Tree)는 그래프의.. 2023. 3. 23. 이전 1 다음
