MST
-
[Algorithm] - 최소 신장 트리Algorithm/Algorithm 2022. 4. 11. 14:27
신장 트리 연결 그래프의 부분 그래프로서 그 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리로 모든 노드는 적어도 하나의 간선에 연결 ( 단 , 싸이클 X ) 아래 그림은 신장트리를 나타난 예시이다. 아래 그림은 신장트리가 아닌 예시이다. Node에 Edge가 연결되지 않거나 , Cycle이 발생되어 Tree의 개념을 상실한 경우이다. 우측 마지막 그림에서는 Edge가 새롭게 생성된 경우이다. 최소 신장 트리 Graph Edge에 Cost가 부여된 그래프를 가중치 그래프 또는 네트워크라고 합니다. 이때 Cost란 비용이나 거리를 의미하는 값이 될 수 있습니다. 신장 트리 비용은 신장 트리를 구성하는 모든 간선의 비용 중 최소의 합 최소 Cost를 알기 위해서는 Edge들의 가중치를 가장 작은것은..