프림 알고리즘 예제

Prim의 알고리즘은 어떻게 작동합니까? Prim 알고리즘의 아이디어는 간단하며 스패닝 트리는 모든 정점을 연결해야 함을 의미합니다. 따라서 스패닝 트리를 만들려면 정점의 두 개의 분리된 하위 집합(위에서 설명한)을 연결해야 합니다. 그리고 최소 가중치 모서리와 연결하여 최소 스패닝 트리로 만들어야 합니다. G=(V, E)를 연결된 가중치 그래프로 만드십시오. Prim 알고리즘의 모든 반복에서 하위 그래프 외부의 정점에 생성되는 하위 그래프의 정점을 연결하는 가장자리를 찾아야 합니다. G가 연결되어 있기 때문에 모든 정점에 대한 경로가 항상 있습니다. Prim 알고리즘의 출력 T는 트리 T에 추가된 가장자리와 정점이 연결되기 때문에 트리입니다. 알고리즘을 구현하는 가장 효율적인 방법은 큐를 사용하는 것입니다. 이 큐는 방문했지만 아직 트리에 추가되지 않은 모든 노드를 추적합니다. 큐에 있는 노드의 순서는 각 노드에서 트리까지의 거리를 사용하여 결정됩니다.

따라서 각 라운드에서 가장 저렴한 가장자리로 트리에 연결된 정점이 큐에서 제거됩니다. 위의 프로그램의 시간 복잡성은 O(V^2)입니다. 입력 그래프가 인접 성 목록을 사용하여 표현되는 경우 Prim 알고리즘의 시간 복잡성을 이진 힙의 도움으로 O(E log V)로 줄일 수 있습니다. 자세한 내용은 인접 목록 표현에 대한 Prim의 MST를 참조하십시오. 큐 작업을 개선하여 알고리즘의 실행 시간을 향상시킬 수 있습니다. Fibonnaci 힙을 사용하여 알고리즘의 실행 시간이 m + n ·로 감소 될 수 있습니다. 로그(n) . (Kruskal의 알고리즘으로) 트리에 걸쳐 최소 비용을 찾기 위해 Prim의 알고리즘은 욕심 접근 방식을 사용합니다. Prim의 알고리즘은 가장 짧은 경로 첫 번째 알고리즘과 유사성을 공유합니다. Dijkstra의 알고리즘은 일부 소스 노드에서 시작하는 최단 경로 트리를 생성합니다. 가장 짧은 경로 트리는 그래프의 모든 노드를 연결하고 루트에서 그래프의 다른 노드까지의 경로 길이가 최소화되는 속성이 있는 트리입니다(아래 그림). Prim의 알고리즘은 그래프의 모든 노드를 연결하고 모든 노드를 연결하는 모든 트리 중에서 가장 적은 총 비용을 가진 트리인 그래프에 대한 최소 스패닝 트리를 생성합니다.

그러나 루트와 MST의 다른 노드 사이의 경로 길이는 원래 그래프에서 두 노드 사이의 가장 짧은 경로가 아닐 수 있습니다. 위의 알고리즘을 구현하는 방법? MST에 포함된 정점 집합을 나타내기 위해 부울 배열 mstSet[]을 사용합니다.

Comments are closed