반응형 최소 신장 알고리즘1 신장 트리 (Spanning Tree) & 크루스칼(Kruskal) 신장트리 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 이러한 성질을 가진 그래프는 다양한 문제에 활용되는데, 대표적인 유형이 여러 노드를 연결하는 간선이 비용을 가질 때, 그 비용의 합이 최소가 되는 신장트리를 찾아야 하는 경우이다. 예를 들어보면, 아래와 같은 그래프가 존재 한다고 한다. 간선의 비용의 합을 최소로 하기는 신장트리가 되기 위해서는 아래와 같이 연결을 해야 할 것이다. 이처럼 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트릴르 찾는 알고리즘을 이제 '최소 신장 트리 알고리즘'이라고 하자. 이러한 최소 신장 트리 문제를 해결하기 위한 대표적인 알고리즘을 다음을 통해 배워보자. 크루스칼 알고리즘 (Kruskal Algorithm) 이는 가장 적은.. 2021. 9. 13. 이전 1 다음 반응형
