PinguiOS

안녕하세요! Ick입니다. 최소 비용 신장 트리 - Minimum Cost Spanning Tree 오늘은 여러 알고리즘 중에서 최소 비용 신장 트리라고 불리는 알고리즘에 대해 알아보려고 합니다! 최소 비용 신장 트리, 최소 스패닝 트리라고 불리는 이 알고리즘은 가중치 무방향 그래프에서 모든 정점을 연결할 때 최소의 비용으로 연결할 수 있는 방법을 찾는 알고리즘입니다. 가중치 무방향 그래프는 무엇일까요? 위와 같이 그래프가 있을 때 정점 사이에 가중치가 있고 간선에 방향이 없는 그래프를 가중치 무방향 그래프라고 합니다. 예를 들어 위의 그래프에서 정점 1에서 정점 3으로 가고 싶다면 25의 가중치를 가진 간선을 사용하면 되는 것입니다. 이번 글에서 배울 최소 비용 신장 트리는 이러한 그래프에서 모든 정점..