Dot Algo∙ DS/알고리즘 개념
2021. 4. 22.
[알고리즘/ 그래프] 최소 스패닝 트리 - 크루스칼(Kruskal)과 프림(Prim) 알고리즘 (Java)
스패닝 트리 또는 신장 트리 어떤 무향 그래프의 스패닝 트리는 원래 그래프의 정점 전부와 간선의 부분 집합으로 구성된 부분 그래프이다. 이때 스패닝 트리에 포함된 간선들은 정점들을 트리 형태로 전부 연결해야 한다. 트리 형태여야 한다는 말은 선택된 간선들이 사이클을 이루지 않는다는 뜻이며, 정점들이 꼭 부모-자식 관계로 연결될 필요는 없다는 데 유의하자. 즉, 스패닝 트리는 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 하다. 최소 스패닝 트리 (MST) 최소 스패닝 트리란 최소한의 비용으로 구성되는 스패닝 트리를 말한다. 두 가지 유명한 알고리즘으로 크루스칼과 프림이 있다. 크루..
![[알고리즘/ 그래프] 최소 스패닝 트리 - 크루스칼(Kruskal)과 프림(Prim) 알고리즘 (Java)](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/bq9IbU/btroDuQIHjW/IN20HC7kdvmljFB4Xq62uk/img.png)