반응형
모든 노드들을 최소한의 비용으로 연결한 트리를 최소신장트리(mst)라고 한다.
최소신장 트리를 만드는 방법은 여러가지가 있다.
1. 크루스칼 알고리즘
1) 모든 간선들을 오름차순으로 정렬한다.
2) 가중치가 작은 간선부터 하나씩 연결한다.
3) 간선을 연결했을 때 사이클이 생기면 해당 간선은 제거하고 다음 간선을 붙인다.
4) 간선의 개수가 (node개수 - 1)이 될때까지 간선을 이어붙인다.
<가장 정리가 잘되어있다>
18. 크루스칼 알고리즘(Kruskal Algorithm)
이번 시간에 다루어 볼 내용은 바로 크루스칼 알고리즘입니다. 크루스칼 알고리즘은 가장 적은 비용으로 모...
blog.naver.com
반응형