Изменения

Перейти к: навигация, поиск

Алгоритм Прима

Нет изменений в размере, 20:30, 11 октября 2014
Пример
|
{| width="100%"
! | '''a''' || '''b''' || '''c''' || '''d''' || '''e'''
|-
! | <tex> 0 </tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>
|}
|style="padding-left: 1em" | Извлечём из множества вершину '''a''', так как её приоритет минимален.<br/>Рассмотрим смежные с ней вершины '''b''', '''c''', и '''e'''. <br/>Обновим их приоритеты, как веса соответствующих рёбер '''ab''', '''ac''' и '''ae''', которые будут добавленны в ответ.
|
{| width="100%"
! | a || '''b''' || '''c''' || '''d''' || '''e'''
|-
! | <tex> 0 </tex> || <tex> 3 </tex> || <tex> 4 </tex> || <tex>\infty</tex> || <tex> 1 </tex>
|}
|style="padding-left: 1em" |Теперь минимальный приоритет у вершины '''е'''.<br/> Извлечём её и рассмотрим смежные с ней вершины '''a''', '''c''', и '''d'''.<br/>Изменим приоритет только у вершины '''d''', так как приоритеты вершин '''a''' и '''с''' меньше,<br/>чем веса у соответствующих рёбер '''ea''' и '''ec''', и установим приоритет вершины '''d''' равный весу ребра '''ed''', которое будет добавленно в ответ.
|
{| width="100%"
! | a || '''b''' || '''c''' || '''d''' || e
|-
! | <tex> 0 </tex> || <tex> 3 </tex> || <tex> 4 </tex> || <tex> 7 </tex> || <tex> 1 </tex>
|}
|style="padding-left: 1em" |После извлечения вершины '''b''' ничего не изменится, так как приоритеты вершин '''a''' и '''с''' меньше,<br/>чем веса у соответствующих рёбер '''ba''' и '''bc'''. Однако, после извлечения следующей вершины - '''c''',<br/>будет обновлён приоритет у вершины '''d''' на более низкий (равный весу ребра '''cd''') и в ответе ребро '''ed''' будет заменено на '''cd'''.
|
{| width="100%"
! | a || b || c || '''d''' || e
|-
! | <tex> 0 </tex> || <tex> 3 </tex> || <tex> 4 </tex> || <tex> 2 </tex> || <tex> 1 </tex>
|}
|style="padding-left: 1em" |Далее будет рассмотрена следующая вершина - '''d''', но ничего не изменится,<br/>так как приоритеты вершин '''e''' и '''с''' меньше, чем веса у соответствующих рёбер '''de''' и '''dc'''.<br/>После этого алгоритм завершит работу, так как в заданном множестве не останется вершин,<br/>которые не были бы рассмотрены
Анонимный участник

Навигация