프림 알고리즘 예제

알고리즘을 구현하는 가장 효율적인 방법은 큐를 사용하는 것입니다. 이 큐는 방문했지만 아직 트리에 추가되지 않은 모든 노드를 추적합니다. 큐에 있는 노드의 순서는 각 노드에서 트리까지의 거리를 사용하여 결정됩니다. 따라서 각 라운드에서 가장 저렴한 가장자리로 트리에 연결된 정점이 큐에서 제거됩니다. Prim의 알고리즘은 어떻게 작동합니까? Prim 알고리즘의 아이디어는 간단하며 스패닝 트리는 모든 정점을 연결해야 함을 의미합니다. 따라서 스패닝 트리를 만들려면 정점의 두 개의 분리된 하위 집합(위에서 설명한)을 연결해야 합니다. 그리고 최소 가중치 모서리와 연결하여 최소 스패닝 트리로 만들어야 합니다. (Kruskal의 알고리즘으로) 트리에 걸쳐 최소 비용을 찾기 위해 Prim의 알고리즘은 욕심 접근 방식을 사용합니다. Prim의 알고리즘은 가장 짧은 경로 첫 번째 알고리즘과 유사성을 공유합니다. 작업은 큐에서 제거된 순서대로 그래프의 노드를 클릭하는 것입니다.

이는 알고리즘을 실행하는 동안 노드가 빨간색으로 표시된 순서에 해당합니다. 우리는 두 개의 서로 다른 알고리즘을 사용하여 동일한 그래프의 트리에 걸쳐 출력이 동일하다는 것을 발견 할 수 있습니다. Prim의 알고리즘은 Kruskal의 알고리즘과 달리 노드를 단일 트리로 처리하고 지정된 그래프에서 스패닝 트리에 새 노드를 계속 추가합니다. G=(V, E)를 연결된 가중치 그래프로 만드십시오. Prim 알고리즘의 모든 반복에서 하위 그래프 외부의 정점에 생성되는 하위 그래프의 정점을 연결하는 가장자리를 찾아야 합니다. G가 연결되어 있기 때문에 모든 정점에 대한 경로가 항상 있습니다. Prim 알고리즘의 출력 T는 트리 T에 추가된 가장자리와 정점이 연결되기 때문에 트리입니다. Kruskal의 알고리즘과 는 달리 더 나은 프림의 알고리즘을 이해하기 위해, 우리는 같은 예를 사용한다 – 프림의 알고리즘은 최소 스패닝 트리 (MST)를 찾을 수있는 한 가지 방법입니다. 큐 작업을 개선하여 알고리즘의 실행 시간을 향상시킬 수 있습니다. Fibonnaci 힙을 사용하여 알고리즘의 실행 시간이 m + n ·로 감소 될 수 있습니다. 로그(n) . Dijkstra의 알고리즘은 일부 소스 노드에서 시작하는 최단 경로 트리를 생성합니다.

가장 짧은 경로 트리는 그래프의 모든 노드를 연결하고 루트에서 그래프의 다른 노드까지의 경로 길이가 최소화되는 속성이 있는 트리입니다(아래 그림). Prim의 알고리즘은 그래프의 모든 노드를 연결하고 모든 노드를 연결하는 모든 트리 중에서 가장 적은 총 비용을 가진 트리인 그래프에 대한 최소 스패닝 트리를 생성합니다. 그러나 루트와 MST의 다른 노드 사이의 경로 길이는 원래 그래프에서 두 노드 사이의 가장 짧은 경로가 아닐 수 있습니다. 위의 알고리즘을 구현하는 방법? MST에 포함된 정점 집합을 나타내기 위해 부울 배열 mstSet[]을 사용합니다. mstSet[v] 값이 true이면 정점 v가 MST에 포함되지만 그렇지 않으면 포함되지 않습니다. 배열 키[]는 모든 정점의 키 값을 저장하는 데 사용됩니다. MST에 상위 노드의 인덱스를 저장하는 또 다른 어레이 부모[]입니다. 상위 배열은 구성된 MST를 표시하는 데 사용되는 출력 배열입니다. Dijikstra 의 알고리즘에서 이러한 기능을 제공하기 위해 거리 배열은 새 가장자리의 가중치와 루트에서 부모 노드의 길이의 합계를 사용하여 업데이트됩니다. 그러나 Prim의 알고리즘에서는 거리 배열을 업데이트하는 데 새 가장자리의 가중치(MST에서 새 노드의 거리)만 사용됩니다.

Uncategorized