Minimum spanning tree

크루스칼 알고리즘 (Kruskal Algorithm) 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 '최소 신장 트리 알고리즘' 이라고 하는데, 대표적인 최소 신장 트리 알고리즘으로는 크루스칼 알고리즘 이 있다. 크루스칼 알고리즘 을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있다. 크루스칼 알고리즘은 대표적인 최소 신장 트리 알고리즘 이다. 그리디 알고리즘으로 분류된다. 그렇다면, 신장 트리란 무엇인가? 신장 트리 란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. → 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는 다는 조건은 트리 의 성립 조건이기도 함. 신장 트리는 알겠고.. 그러면 최소 신장 ..