Обсуждение:Алгоритм Прима
Эта статья тематически связана с вики-проектом «Математика», цель которого — создание и улучшение статей по темам, связанным с математикой. Вы можете её отредактировать, а также присоединиться к проекту, принять участие в его обсуждении и поработать над требуемыми статьями. |
Untitled править
Почему в разделе «Реализация» описан алгоритм Краскала (почти дословный копипаст)? В Приме выбирается ребро не (из всех доступных и наименьшего веса и не приводящих к циклам), а (из рёбер, ведущих из вершин в дереве к вершинам вне дерева и минимального веса) --Джус 14:34, 26 августа 2007 (UTC)
T ← {} Для каждой вершины i∈V d[i]←∞ p[i]←nil
d[1]←0 Q←V i← Extract.min(Q) Пока Q не пуста Для каждой вершины u смежной с V
Если u∈Q и w(v,u) < d[u] d[u]←w(v,u) p[u]←v
v←Extract.Min(Q) T←T + (p[v],v)
если учесть, что V - это МНОЖЕСТВО всех вершин, то ошибка очевидна. откуда здесь " Если u∈Q и w(v,u) < d[u] " взялось v, если инициализируется она в предпоследней строке?
Думается мне, правильный вариант выглядит так: T← {} Для каждой вершины i∈V
d[i]←∞ p[i]←nil
d[1]←0 Q←V v← Extract.min(Q) Пока Q не пуста
Для каждой вершины u смежной с v
Если ( u ∈ Q ) и ( w(v,u) < d[u] ) d[u]←w(v,u) p[u]←v
v←Extract.Min(Q) T←T + (p[v],v)
Если не будет других мнений, через пару дней сохраню в статью ost. 11:05, 18 февраля 2009 (UTC)
Вы правы, ошибся в обозначениях 78.29.83.20 09:16, 28 февраля 2009 (UTC)