728x90 반응형 Kruskal Algorithm1 [Algorithm] 프림 알고리즘(Prim algorithm)과 크루스칼 알고리즘 (Kruskal algorithm) 다음과 같은 그래프가 있다고 해보자. 신장 트리는 그래프의 부분적인 트리라고 볼 수 있는데 그래프의 모든 노드를 갖고 있지만 에지의 경우 사이클이 생기지 않는 최소 부분만 가지고 있는 트리이다. 위의 그래프의 신장 트리는 여러 경우의 수가 존재한다. 많기 때문에 일부만 소개한다. 최소 신장 트리란 가중 그래프의 신장 트리 중에서 가장 가중치의 합이 작은 트리를 의미한다. 이렇나 최소 신장 트리를 구하는 방법인 Prim's algorithm과 Kruskal's algorithm에 대해서 공부해보려 한다. Prim algorithm 노드 하나를 선택한다. 선택된 노드들과 이어진 노드들 중 가장 가중치가 적은 노드를 고른다. 지금까지 선택된 노드들과 연결된 노드들 중 가장 가중치가 적은 노드를 고른다. 위 방.. 2022. 12. 17. 이전 1 다음 728x90 반응형
