huhsae's day huhsae's day

MTSMTS, 최소신장트리, 최소스패닝트리 최소신장트리는 이름에서 알 수 있듯이 트리와 관련되어있다. 정확히 따지자면 그래프에서 특정 트리를 찾아내는 것이다. 주어진 그래프에서 모든 노드를 포함하는 가중치가 최소(또는 최대)가 되는 트리를 찾는 것이다. 왜 신장이라는 단어가 들어가는 지는 잘 모르겠지만, 모든 노드를 포함하는 중복되는 간선이 없음을 뜻하는 것일 듯 하다. 즉 간선의 수는 무조건 노드의 수보다 하나 작아야 한다는 것이다. 또 다른 조건은 앞에서 설명했던 내용에서 유추할 수 있듯이 사이클이 발생해서는 안된다는 것이다. 트리, 그래프에서 대해서 모른다면 다른 곳에서 찾아보고 오자. Kruskal & Prim 최소신장트리를 구하는 알고리즘은 Prim과 Kruskal알고리즘이 있다. 포인트는 Kr..