최소스패닝트리1 크루스칼 알고리즘 (최소스패닝트리,cut property, disjoint set 에 기반하여.) 크루스칼 알고리즘은 최소스패닝 트리를 구하는 알고리즘 중 하나이다. 우선 스패닝 트리에 대해알아보자. 스패닝트리 : 그래프의 모든 노드를 포함하는 트리. -> 즉 한붓그리기 가능하면 그 한붓을 스패닝트리 라고함. 한가지 그래프가 있으면 여러개의 스패닝트리가 존재한다. 스패닝트리의 weight = 그 스패닝트리의 가중치합. 스패닝 트리들 중에 weight 가 최소인거 : 최소스패닝 트리. -> 즉 최소스패닝트리 : 그래프의 모든 노드를 포함하는 트리중에 간선 가중치의 합이 최소인 트리. 최소스패닝 트리 구하는 알고리즘중 하나인 크루스칼 알고리즘, 이제좀 감이 잡힌다. 배워보려고 하는데 여기서 우선, 컷정리(cut property) 를 알아야 크루스칼 알고리즘을 배울수있다. 컷 프로퍼티란? 컷.. 2021. 5. 20. 이전 1 다음 반응형