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

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

1 голос
/ 19 декабря 2009

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

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

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

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

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

Теперь сначала установите v <---- узел b. Затем проверьте, принадлежит ли v Q. Это так. Проверьте, что w (u, v) <ключ [v]. Правда. Так что PI [v] <--- u и ключ [v] <--- w (u, v). Я получил это много. Это показано в (b) диаграммы на стр. 12. </p>

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

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

Aaaaaah! Почему?

Ответы [ 2 ]

4 голосов
/ 20 декабря 2009

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

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

* Ваш анализ на самом деле полностью верен, но вы (и я) были сбиты с толку о том, что означает обновление ключа [v] и pi (v). В в частности, когда вы обновляете pi (v), вы не добавляете его в дерево. узел 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 не извлечены из Q). Это завершает шаг (а)
  • (строка 6) Узел u с минимальным ключом (который теперь является узлом b, с key = 4) удаляется из Q и добавляется в дерево через его родителя (который является пи (б) = а)
  • (строки 8-11) Ключ узлов c обновляется до 8, а pi (c) устанавливается на б. Поскольку ключ (h) = 8 меньше, чем 11 = w (b, h), ключ и родитель h не обновляются. Это завершает шаг (б)
  • (строка 6) Узел u с минимальным ключом (узел c, с ключом = 8, но это также мог быть узел h, который также имеет ключ = 8) удаляется из Q и добавлен в дерево через его родителя (который является пи (с) = b)
  • (строки 8-11) Обновление ключей и родителей узлов d, i и f, завершение шага (c)
  • и др. *
0 голосов
/ 20 декабря 2009

Ваше описание верно, алгоритм устанавливает ключ [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
...