최소 신장 트리(최소 스패닝 트리, MST, Minimum Spanning Tree)

알고리즘 설명 최소 신장 트리(최소 스패닝 트리, MST, Minimum Spanning Tree) KQNG 2018. 7. 17. 16:41 이웃추가 본문 기타 기능 이번 포스트에선 최소 신장 트리에 대해 설명하겠습니다. 우선 신장 트리는 그래프가 주어지면 만족해야하는 세가지 조건이 존재합니다. 1.

모든 정점을 포함해야 한다. 2. 모든 정점은 직접, 간접적으로 연결되어야 한다. 3.

트리의 속성을 만족해야한다. 따라서 신장 트리는 다음과 그림과 같이 여러개가 존재할 수 있습니다.

(발그림 주의) 그 중에서 최소 신장 트리는 간선을 연결할 때 일종의 비용이 든다고 가정하였을 때 가장 적은 비용을 들여 만들 수 있는 신장트리를 의미합니다. 임의로 비용을 준 정점과 간선 그래프의 최소 신장 트리는 다음과 같습니다.

(발전한 발그림) 왼쪽의 정점 4개와 비용이 주어진 간선들이 존재할 때 신장 트리를 만들려고 할 때 1, 2, 3의 비용을 들여 선을 3개 그려준 우측 모양의 그래프가 최소 ...

요청 처리 중입니다...

최소 신장 트리(최소 스패닝 트리, MST, Minimum Spanning Tree)

등록된 다른 글