이 포스트에서 우리는 Prim과 Kruskal의 알고리즘의 차이점을 이해할 것입니다.
최소 스패닝 트리(MST)에 대한 Kruskal 알고리즘
- 연결된 그래프와 방향이 없는 그래프가 주어졌을 때 이러한 그래프의 스패닝 트리는 모든 정점을 연결하는 트리인 하위 그래프입니다.
- 단일 그래프에 여러 스패닝 트리가 있을 수 있습니다.
- 가중, 연결 및 무방향 그래프에 대한 MST(최소 가중치 스패닝 트리라고도 함)는 다른 모든 스패닝 트리의 가중치보다 작거나 같은 스패닝 트리입니다.
- 스패닝 트리의 가중치는 스패닝 트리의 모든 가장자리와 관련된 가중치를 더하여 결정됩니다.
- 최소 스패닝 트리는 그래프에서 최소 가중치를 갖는 꼭짓점에서 만들 수 있습니다.
- 한 노드는 한 번만 통과합니다.
- 희소 그래프에서 빠르게 실행됩니다.
- 시간 복잡도는 O(E log V)이며, 여기서 V는 정점의 수입니다.
- 연결이 끊긴 구성 요소에서도 작동할 수 있습니다.
Kruskal 알고리즘을 사용하여 MST를 찾는 단계:
- 가장자리를 관련 가중치의 오름차순으로 정렬합니다.
- 가장 작은 가장자리를 선택합니다.
- 그 시점까지 형성된 스패닝 트리와 순환을 이루는지 확인합니다.
- 사이클이 형성되지 않은 경우 이 모서리를 포함해야 합니다.
- 그렇지 않으면 폐기될 수 있습니다.
- 스패닝 트리에 V-1 에지가 포함될 때까지 2,3,4단계를 반복합니다.
Prim의 알고리즘 MST(Minimum Spanning Tree)
- 이것은 Kruskal의 알고리즘과 유사합니다. 즉, 욕심 많은 알고리즘입니다.
- 빈 스패닝 트리로 시작합니다. 두 세트의 정점이 유지됩니다.
- 첫 번째 집합은 MST에 이미 포함된 꼭짓점을 포함하고 다른 집합에는 아직 포함되지 않은 꼭짓점을 포함합니다.
- 모든 단계에서 알고리즘은 두 세트를 연결하는 모든 가장자리를 고려합니다. 그런 다음 이 가장자리 중에서 최소 가중치 가장자리를 선택합니다.
- 이 단계 후에 알고리즘은 MST를 포함하는 집합 가장자리의 다른 끝점으로 이동합니다.
- 최소 스패닝 트리는 그래프의 모든 정점에서 만들 수 있습니다.
- 하나의 노드는 최소 거리 값을 얻기 위해 여러 번 이동합니다.
- 시간 복잡도는 O(V2)이며, 여기서 V는 꼭짓점의 수입니다. 이 시간 복잡도는 피보나치 힙을 사용하여 O(E + log V)로 향상될 수 있습니다.
- 밀도가 높은 그래프에서 빠르게 실행됩니다.
- 연결된 구성 요소를 제공하며 연결된 그래프에서만 작동합니다.
Prim의 알고리즘을 사용하여 MST를 찾는 단계:
- 이미 MST에 포함된 정점을 추적하는 mstSet이 생성됩니다.
- 입력 그래프의 모든 정점에 키 값이 할당됩니다.
- 키 값은 초기에 'INFINITE'로 지정됩니다.
- 키 값 0은 첫 번째 정점에 할당되어 먼저 선택될 수 있습니다.
- mstSet에 모든 정점이 포함되지 않은 경우 아래 단계를 따릅니다.
- mstSet에 존재하지 않고 최소 키 값을 갖는 꼭짓점 'u'가 선택되었습니다.
- 이 'u'는 이제 mstSet에 포함됩니다.
- 'u'의 인접한 모든 정점의 키 값이 업데이트됩니다.
- 인접한 모든 정점을 반복하여 수행할 수 있습니다.
- 모든 인접 꼭짓점 'v'에 대해 edge 'u'-'v'의 가중치가 이전 키 값 'v'의 가중치보다 작으면 키 값이 'u-v'의 가중치로 업데이트됩니다. '.