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

Я изучал книгу Кормена и др., и я немного запутался в алгоритме, который они предоставили. Я понял, как работает концепция алгоритма Прима из Википедии, но я не могу имитировать эту работу, используя алгоритм, представленный в моей книге.

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

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

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

u ‹--- узел A через ExtractMin(Q). Далее, согласно диаграмме, в Adj[u] есть две записи: узел b и узел h.

Теперь сначала установите v ‹---- node b. Затем проверьте, принадлежит ли v Q. Принадлежит. Проверить, является ли w(u,v) ‹ key[v]. Истинный. Итак, PI[v] ‹--- u и key[v] ‹--- w(u, v). Я получил это много. Это показано в (b) диаграммы на стр. 12.

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

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

Аааааа! Почему?


algorithm prims-algorithm minimum-spanning-tree
person Arrrr    schedule 19.12.2009    source источник
comment
Вы можете задать этот вопрос на mathoverflow.net.   -  person Greg Hewgill    schedule 19.12.2009
comment
Вау, этот вопрос не получил там очень теплого приема. Это не то, чего я ожидал.   -  person Greg Hewgill    schedule 19.12.2009

Ответы (2)


arrow_upward
4
arrow_downward

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

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

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

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

arrow_upward
0
arrow_downward

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

Шаг 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
person Keith Randall    schedule 20.12.2009