Алгоритм Prim для минимальных связующих деревьев - путаница в алгоритме

Question

Я изучаю книгу Cormen и др., И я немного смущен относительно алгоритма, который они предоставили. Я понял, как концепция алгоритма Prim's работает через википедию, но я не могу имитировать работу, используя алгоритм, приведенный в моей книге.

Обратитесь к этой онлайн-копии главы: http://www.cs.cmu.edu/afs/cs/academic/class/15451-s04/www/Lectures/minimumSpanningTrees.pdf

алго приведена на странице 13 в приведенной выше ссылке и пример диаграмма на предыдущей странице.

Теперь, с помощью алгоритма на примере случая, на первом этапе:

< U --- узел А через ExtractMin (Q). Тогда в Adj [u] есть две записи в соответствии с диаграммой: узел b и узел h.

В настоящее время первый набор v < ---- узел b. Затем проверьте, принадлежит ли v классу Q. Это делает. Проверьте, есть ли w (u, v) < ключ [v]. Правда. Таким образом, PI [v] < --- u и клавиша [v] < --- w (u, v). У меня это получилось. Это показано в (b) диаграммы на pg 12.

НО, а в алго говорится «для каждого v в Adj [u]».

Итак, следующий шаг должен установить v < --- узел h. Затем проверьте, принадлежит ли v к Q. Это так! И есть w (u, v) < ключ [v]? Это! Поскольку ключ [v] = бесконечность! Но диаграмма показывает другой шаг в части (c)!

Aaaaaah! Зачем?

Answer 1

Ваше описание верное, алгоритм устанавливает ключ [h] = 8, как описано на шаге a.

Шаг c имеет ключевой галстук, вы можете выбрать h, если хотите, но пример выбирает c вместо этого.

Лучший способ увидеть это, чтобы увидеть, что (не бесконечна) элементы находятся в приоритетной очереди на каждом шаге (как раз перед ExtractMin):

1: Q = (a, 0)   - removes a, sets key[b]=4, key[h]=8 
2: Q = (b, 4), (h, 8) - removes b, sets key[c]=8 
3: Q = (h, 8), (c, 8) - could pick either h or c, they have the same key 

Answer 2

Один из парней в МО был вид достаточно ответить по электронной почте. Проблема заключалась в том, что я не заметил, что узлы дерева добавляются по одному за счет операции ExtractMin (Q).

Вот ответ он дал:

* Ваш анализ на самом деле совершенно правильно, но вы (и я) были смущены о том, что ключ обновления [v] и р (v) означает. В особенно, когда вы обновляете pi (v), вы не добавьте его в дерево. A узел u добавляется к дереву (вдоль края, соединяющего его с его родительским pi (u)) только тогда, когда он извлекается из Q. Так что все продолжается , как вы описали, но в конце этого вы только завершенный шаг (a), а не шаг (c). Вот изношенный о том, что программа делает в этом случае :

• (строки 1-3) Все узлы размещаются в Q (множество узлов не в дереве), их родители были объявлены в быть NIL и их ключ (т.е. минимального расстояния до существующего дерева вдоль одного края) установлено на бесконечности
• (строка 4) Ключ корневого узла (узел а) устанавливаются на 0
• (строка 6) узел ЕВ с минимальным ключ (который является корневым узлом a) равен , удаленный из Q и добавленный к дереву
• (строки 8-11) Ключи узлов b и h обновляются до 4 и 8 и pi (b) и pi (h) установлены на u (но b и h равны , а не, извлеченным из Q). Это завершает стадию (а)
• (строка 6) узел ЕВ с минимальным ключом (который в настоящее время узел B, с ключ = 4) удаляется из Q и добавляется к дереву с помощью своего родителя (который пи (b) = a)
• (строки 8-11) Ключ узлов c обновлен до 8, а pi (c) установлен в b. Поскольку ключ (h) = 8 меньше 11 = w (b, h), ключ и родительский элемент h не обновляются. На этом этапе завершается этап (b)
• (строка 6) Узел u с минимальным ключом (узел c с ключом = 8, но он также мог быть узлом h, который также имеет ключ = 8) удаляется из Q и добавляется к дереву через его родительский элемент (который представляет собой pi (c) = b)
• (строки 8-11) Обновить ключи и родители узлов d, i и f, шаг завершения (c)
• и т. д. *