2022/07/28

[바미] 최소 신장 트리(MST, Minimum Spanning Tree)란

안녕하세요. 오늘은 최소 신장 트리에 대해 알아보도록 하겠습니다. Spanning Tree란? 그래프 내의 모든 정점을 포함하는 트리를 말합니다. Spanning Tree = 신장 트리 = 스패닝 트리입니다. Spanning Tree는 그래프의 최소 연결 부분 그래프입니다. 최소 연결 = 간선의 수가 가장 적습니다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 됩니다. 그러므로, 그래프에서 일부 간선을 선택해서 만든 트리가 되죠. Spanning Tree의 특징 DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있습니다. 탐색 도중에 사용된 간선만 모으면 만들 수 있습..