Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 128 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова .
№
Действия с
комментариями
Тек.
вер-
шина
Состояние
массива
ребер
ostov
Состояние
массива
вершин в
каркасе
nodes
Состояние мас-
сивов
ближайших вер-
шин alpha и
длин beta
5
Находим в массиве
beta минимальный эле-
мент среди тех, которые
соответствуют верши-
нам, не включенным в
nodes: beta[3]=3.
Включаем вершину 3 в
массив nodes, а ребро
<2, 3> в каркас. Верши-
на 3 становится теку-
щей.
3
{<1,2>,
<2,3>}
{1, 2, 3}
alpha = {0, 1, 2,
1, -1, 2}
beta = {0, 7, 2,
8, ∝, 6}
6
Изменяем массивы
alpha и beta. Смеж-
ной с вершиной 3 яв-
ляется вершина 6. В
beta заносим длину ре-
бра из вершины 3 в вер-
шину 6, в alpha – но-
мер текущей вершины 3.
3
{<1,2>,
<2,3>}
{1, 2, 3}
alpha = {0, 1, 2,
1, -1, 3}
beta = {0, 7, 2,
8, ∝, 3}
7
Находим в массиве
beta минимальный эле-
мент среди тех, которые
соответствуют верши-
нам, не включенным в
nodes: beta[6]=3.
Включаем вершину 6 в
массив nodes, а ребро
<3, 6> в каркас. Верши-
на 6 становится теку-
щей.
6
{<1,2>,
<2,3>,
<3,6>}
{1, 2, 3, 6}
alpha = {0, 1, 2,
1, -1, 3}
beta = {0, 7, 2,
8, ∝, 3}
Таблица 4. Построение каркаса минимального веса алгоритмом Прима.
Продолжение.
128
А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова                                  .
                                                       Состояние      Состояние мас-
                                           Состояние                      сивов
                                  Тек.                  массива
           Действия с                       массива                   ближайших вер-
№                                 вер-                 вершин в
         комментариями                       ребер                     шин alpha и
                                  шина      ostov       каркасе
                                                        nodes           длин beta

    Находим в массиве
    beta минимальный эле-
    мент среди тех, которые
    соответствуют верши-                                              alpha = {0, 1, 2,
    нам, не включенным в                     {<1,2>,                      1, -1, 2}
5   nodes:      beta[3]=3.          3                   {1, 2, 3}
    Включаем вершину 3 в                     <2,3>}                   beta = {0, 7, 2,
    массив nodes, а ребро                                                 8, ∝, 6}
    <2, 3> в каркас. Верши-
    на 3 становится теку-
    щей.

    Изменяем       массивы
    alpha и beta. Смеж-
                                                                      alpha = {0, 1, 2,
    ной с вершиной 3 яв-
    ляется вершина 6. В                      {<1,2>,                      1, -1, 3}
6   beta заносим длину ре-          3                   {1, 2, 3}
                                             <2,3>}                   beta = {0, 7, 2,
    бра из вершины 3 в вер-
    шину 6, в alpha – но-                                                 8, ∝, 3}
    мер текущей вершины 3.

    Находим в массиве
    beta минимальный эле-
    мент среди тех, которые
    соответствуют верши-                                              alpha = {0, 1, 2,
                                             {<1,2>,
    нам, не включенным в                                                  1, -1, 3}
7   nodes:      beta[6]=3.          6        <2,3>,    {1, 2, 3, 6}
    Включаем вершину 6 в                                              beta = {0, 7, 2,
                                             <3,6>}
    массив nodes, а ребро                                                 8, ∝, 3}
    <3, 6> в каркас. Верши-
    на 6 становится теку-
    щей.




             Таблица 4. Построение каркаса минимального веса алгоритмом Прима.
                                                                  Продолжение.
                                           128

Страницы