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