[자료구조] 신장 트리, 최소 비용 신장 트리 (Spanning Tree)
신장 트리(Spanning Tree)란? 아래 조건을 만족하는 그래프를 의미합니다. 1. 연결 그래프의 부분 그래프이며, 그래프에서 모든 정점을 포함합니다. 2. 정점 간 서로 연결이 되어있어야 합니다. 3. 사이클이 존재하지 않는 그래프 4. 연결 그래프에서 신장트리는 1개가 아닌 다수일 수 있습니다. 아래 그림은 연결 그래프를 다양한 신장트리로 표현한 예입니다. 최소 비용 신장 트리(MST - Minimum Cost Spanning Tree)란? 1. 트리를 구성하는 간선들의 가중치를 합한 값이 최소가 되는 신장 트리입니다. 2. 가중치 무방향 그래프가 베이스일때 구할 수 있습니다. 3. MST를 찾아내는 방법은 다양하며 대표적으론 (크루스칼, 프림) 알고리즘이 있습니다. [크루스칼 알고리즘 정리] ..
Data Structure
2020. 11. 6. 21:45