최소 신장 트리 (MST)

Overview 최소 신장 트리(Minimum Spanning Tree | MST)란 한 그래프에 속해 있는 모든 정점을 잇는 최소 비용의 부분 그래프를 의미합니다. 다시 말해서, 가장 적은 비용으로 모든 정점들을 이어주는 그래프를 의미하는 것입니다. 네트워크 장비에 관한 포스팅에서 스위치(네트워크 장비)를 통해 여러 개의 컴퓨터들을 연결하는 과정에 대해서 살펴보았습니다. 이 때, 컴퓨터 사이에 두 개 이상의 네트워크 경로가 존재할 경우, 네트워크 루핑 현상이 발생할 수 있으며, 이를 막기 위해 스위치는 스패닝 트리 프로토콜을 통해 컴퓨터와 컴퓨터 사이에는 단 하나의 루트만 존재하게끔 조정해 줍니다. 이 스패닝 트리 프로토콜이 바로 최소 스패닝 트리와 밀접하게 연관되어 있습니다. 최소 신장 트리는 최소 ..

2020.06.27