피보나치 힙으로 Prim의 알고리즘을 구현하는 방법은 무엇입니까?

Question

나는 Prim's algorithm을 알고 있으며 그 구현을 알고 있지만 항상 지금 물어보고 싶은 부분은 건너 뜁니다.

• 브리핑에서 피보나치 힙 것입니다 : 그것은 Fibonacci heap와 프림의 알고리즘 구현 O(E + V log(V)) 및 내 질문이다라고 쓰여진?
• 어떻게 구현 되나요? 그리고
• 어떻게 피보나치 힙으로 Prim 알고리즘을 구현할 수 있습니까?

Answer 1

피보나치 힙이 뛰어난이 모든 작업에 점근 행동 amoritzed있는 매우 복잡한 우선 순위 큐입니다 - 삽입을 찾을 분, 및 감소 모두 열쇠 상각 된 O (lg n) 시간 동안 삭제 및 추출 - 분이 실행되는 동안 O (1) 상각 시간으로 실행됩니다. 주제에 대한 좋은 참조를 원하면 CLRS에서 "Introduction to Algorithms, 2nd Edition"의 사본을 가져 와서 해당 장을 읽는 것이 좋습니다. 그것은 아주 잘 쓰여졌 고 아주 잘 묘사되어 있습니다. The original paper on Fibonacci heaps by Fredman and Tarjan은 온라인에서 사용할 수 있으며이를 확인하고 싶을 수도 있습니다. 밀도가 높지만 소재를 잘 처리합니다.당신은 피보나치 힙과 프림 알고리즘의 구현을보고 싶은 경우

, 나는 내 자신의 구현을위한 뻔뻔한 플러그를주고 있습니다

1. My implementation of a Fibonacci heap.
2. My implementation of Prim's algorithm using a Fibonacci heap.

이 두 구현의 주석은 어떻게 작동하는지에 대한 꽤 좋은 설명을 제공해야합니다. 내가 명확히하기 위해 할 수있는 일이 있으면 알려줘!

Answer 2

Prim의 알고리즘은 이미 선택된 와류 그룹과 나머지 와류의 무게가 가장 낮은 에지를 선택합니다.
Prim의 알고리즘을 구현하려면 최소 힙이 필요합니다. 모서리를 선택할 때마다 이미 선택한 소용돌이 그룹에 새 소용돌이를 추가하면 모든 인접한 모서리가 힙으로 이동합니다.
그런 다음 힙에서 최소값을 가진 가장자리를 다시 선택합니다.

그래서 우리가 얻는 시간은 :
피보나치 :
최소 가장자리를 선택 = O (최소 제거 시간) = O (로그 (E)) = O (로그 (V))
삽입 가장자리 힙 = O = 1

최소 힙 (힙 항목에 삽입하는 시간) : 최소 에지 선택
를 = O = O (로그 (E)) = O (힙 최소 제거 시간() log (V))
= O (로그 (E)) = O (로그 (V)가)

(기억 즉 E = ~ V^2 (힙 아이템을 삽입하는 시간) = 힙 O 에지 넣기 .. 그래서 로그인

그래서 전체적으로 E 삽입과 V 최소 선택이 있습니다 (결국 트리입니다). (E) == log (V^2) == 2Log (V) .

그래서 최소의 당신이 얻을 것이다 힙 :

O (동영상 블로그 (V) + ELOG (V)) == O (ELOG (V))

그리고 피보나치에서 당신을 힙 ' LL 얻을 :

O (동영상 블로그 (V) + E)

Answer 3

필자는 몇 년 전에 피보나치 힙을 사용하여 Dijkstra를 구현했으며 문제는 매우 비슷합니다. 기본적으로 피보나치 힙의 장점은 세트의 최소값을 일정한 연산으로 찾는 것입니다. Prim 및 Dijkstra에 매우 적합합니다. 각 단계에서이 작업을 수행해야합니다.

이 좋은 이유

이항 힙 (더 "표준"방법이다)을 사용하는 알고리즘의 복잡성 때문에, (* V 로그 E) O입니다 - 약 - 당신은 모든 가장자리를 시도 할 것이다 (E), 각각에 대해 이진 버텍스를 이진 힙 (로그 V)에 추가하거나 키 (로그 V)를 줄인 다음 힙 (다른 로그 V)의 최소값을 찾아야합니다.

대신 피보나치 힙을 사용하면 힙에 버텍스를 삽입하거나 키를 줄이는 비용이 일정하므로 O (E) 만 있습니다. 그러나 정점을 삭제하는 것은 O (log V)이므로 결국 모든 O (V * log V)를 추가하는 모든 정점이 제거되므로 총 O (E + V * log V)에 대해 정점을 삭제합니다.

그래서 그래프의 밀도가 충분히 높으면 (예 : E >> V), 피보나치 힙을 사용하면 이항 힙보다 낫습니다.

아이디어가 이어지는 작은 가장자리의 무게에 의해 색인이 이미 구축 된 하위 트리에서 액세스 할 수있는 모든 정점을 저장하는 피보나치 힙을 사용하는 것이 얼마나을

. 다른 데이터 구조를 사용하여 구현이나 Prim의 알고리즘을 이해했다면 피보나치 힙을 사용하는 데 실제로 어려움이 없습니다. 평소처럼 삽입 및 deletemin 힙의 메소드를 사용하고 감소 키 꼭지점으로가는 가장자리를 해제 할 때 꼭지점을 업데이트하는 방법.

어려운 부분은 실제 피보나치 힙을 구현하는 것입니다.

여기서 모든 구현 세부 사항을 제공 할 수는 없지만 (페이지를 차지함), 내 경우에는 Introduction to algorithms (Cormen et al)에 많이 의존합니다. 아직 가지고 있지 않지만 알고리즘에 관심이 있다면 그 사본을 얻는 것이 좋습니다! 언어에 구애받지 않으며 모든 표준 알고리즘과 그 증명에 대한 자세한 설명을 제공하며 지식과 모든 기능을 사용하고 새로운 기능을 설계하고 증명할 수있는 능력을 확실히 높여줍니다. This PDF (링크 된 Wikipedia 페이지에서 제공)은 구현 세부 사항 중 일부를 제공하지만 명확하게 알고리즘 소개처럼 명확하지 않습니다.(다 익스트라를 위해 - 의사 코드에서 피보나치 힙 함수에 대한 PPT의 끝을 참조)

내가 진행하는 방법을 조금 설명 report 내가 그 일을 한 후 쓴 presentation을 가지고 있지만, 프랑스어로 모든입니다. .. 그리고 내 code Caml (그리고 프랑스어) 그래서 도움이 될지 모르겠다! 그리고 만약 당신이 그것의 무언가를 이해할 수 있으면 제멋대로합니다. 제 프로그래밍 기술은 그 당시 꽤 가난했습니다. 그래서 프로그래밍을 시작했습니다 ...