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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

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

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

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

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




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

№         Действия с            Тек.    Состояние    Состояние       Состояние мас-

                                        129

Страницы