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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

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

    Включаем в каркас вер-
1   шину 1                      1        пуст          {1}               –

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

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

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




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


                                      127

Страницы