자료구조&알고리즘
[알고리즘] 최소 신장 트리 - 크루스칼 알고리즘
신장 트리(Spanning Tree) 신장 트리란 아래의 조건을 만족하면서 모든 노드가 연결되어 있는 Tree 구조를 말함 모든 노트가 서로 연결되어 있어야 한다. 사이클이 존재하지 않아야 한다.(Tree의 속성) 왼쪽이 Original graph이고 오른쪽이 Original graph에서 나올 수 있는 신장 트리이다. 최소 신장 트리(MST) Minimum Spanning Tree(MST)라고도 불리며 Spanning Tree의 간선 가중치 값이 최소인 Tree를 말함 최소 신장 트리 알고리즘 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재함 대표적인 최소 신장 트리 알고리즘 Kruskal's algorithm (크루스칼 알고리즘), Prim's algorithm(프림 알고리즘) 크루스칼 알..
