minimum spanning tree
-
[Data Structure] Minimum Spanning TreeCS/Data Structure 2021. 10. 8. 09:03
이 포스팅은 세미나를 위해 https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure를 참고하여 작성하였습니다. Spanning Tree 그래프 내의 모든 정점을 포함하는 트리 Spanning Tree는 그래프의 최소 연결 부분 그래프이다. n개의 정점을 가지는 그래프의 최소 간선의 수는 n-1개이고, n-1개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 된다. 이것이 Spanning Tree이다. Minimum Spanning Tree Spnning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리 MST 구현 방법 Kruskal Algorithm 각 단계에서 사이클을 이루지 않는 최소 비용 ..