728x90 반응형 Complete Graph1 [Algorithm] 최소 신장 트리(MST, Minimum Spanning Tree) 개요 ◎ 최소 신장 트리란? ◎ 신장 트리란? ◎ 그림 예시 ◎ 신장 트리 특징 ◎ 최소 신장 트리 구현 알고리즘 안녕하세요. J4J입니다. 이번 포스팅은 최소 신장 트리에 대해 적어보는 시간을 가져보려고 합니다. 최소 신장 트리란? 최소 신장 트리는 신장 트리들 중 가중치의 합이 가장 작은 신장 트리를 의미합니다. 여기서 가중치라고 하는 것은 그래프에서 길(간선)을 지나기 위해 지불되는 값이라고 생각하면 됩니다. 예를 들어 A에서 출발하여 C에 도착한다고 가정해 보겠습니다. A→B 가중치: 5 B→C 가중치: 8 이면 A→C로 이동하기 위한 가중치의 합은 13이 되는 것입니다. 신장 트리란? 신장 트리란 최소한의 길(간선)을 이용하여 모든 정점들을 이동 가능하도록 만들어진 트리입니다. 따라서 하나의 그.. 2021. 1. 24. 이전 1 다음 728x90 반응형
