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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова .
комментариями
вер-
шина
массива
ребер
ostov
массива
вершин в
каркасе
nodes
сивов
ближайших вер-
шин alpha и
длин beta
11
Находим в массиве
beta минимальный
элемент среди тех, ко-
торые соответствуют
вершинам, не вклю-
ченным в nodes:
beta[4]=2. Включа-
ем вершину 4 в массив
nodes, а ребро <4, 5>
в каркас. Вершина 4
становится текущей.
4
{<1,2>,
<2,3>,
<3,6>,
<5, 6>,
<4, 5>}
{1, 2, 3,
6, 5, 4}
–
В каркас добавлены все вершины. Решение получено.
// определение функции построения каркаса минимального веса
// для графа с помощью алгоритма Прима
void Prim(Graph2 g, Edge*& ostov)
{
// выделение памяти под массив ребер каркаса
ostov=new Edge[g.n-1];
// выделение памяти под массив включенных
// в каркас вершин
int* nodes=new int[g.n];
// выделение памяти под вспомогательные массивы
// ближайших вершин из каркаса и расстояний до них
int* alpha=new int[g.n];
int* beta=new int[g.n];
// включение в каркас нулевой вершины и инициализация
// вспомогательных массивов согласно матрице смежности
nodes[0]=0;
int count=1, u=0, v, w, i, ii, min, flag;
for(v=1;v<g.n;v++)
if(g.a[0][v]!=MAX_INT)
{
// если v смежна нулевой вершине
alpha[v]=0;
beta[v]=g.a[0][v];
}
else
130
А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова                              .
                                                        массива        сивов
                                            массива                ближайших вер-
                                  вер-                 вершин в
          комментариями                      ребер                  шин alpha и
                                  шина      ostov       каркасе
                                                        nodes        длин beta

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

               В каркас добавлены все вершины. Решение получено.


     // определение функции построения каркаса минимального веса
     // для графа с помощью алгоритма Прима
     void Prim(Graph2 g, Edge*& ostov)
     {
           // выделение памяти под массив ребер каркаса
           ostov=new Edge[g.n-1];
           // выделение памяти под массив включенных
           // в каркас вершин
           int* nodes=new int[g.n];
           // выделение памяти под вспомогательные массивы
           // ближайших вершин из каркаса и расстояний до них
           int* alpha=new int[g.n];
           int* beta=new int[g.n];
           // включение в каркас нулевой вершины и инициализация
           // вспомогательных массивов согласно матрице смежности
           nodes[0]=0;
           int count=1, u=0, v, w, i, ii, min, flag;
           for(v=1;v

Страницы