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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

. Практикум по курсу «Алгоритмизация и программирование». Часть 2
{
// если v не смежна нулевой вершине
alpha[v]=-1;
beta[v]=MAX_INT;
}
for(i=0;i<g.n-1;i++)
{
// поиск ближайшей вершины среди невключенных
// в каркас
min=MAX_INT;
for(v=1;v<g.n;v++)
{
// проверка на включение вершины в каркас
flag=0;
for(int ii=0; ii<count; ii++)
if(nodes[ii]==v)
flag=1;
if(flag==0)
if(beta[v]<min)
{
w=v;
min=beta[v];
}
}
// включение найденной вершины в каркас
nodes[count]=w;
count++;
// включение ребра <w, alpha[w]> в каркас
ostov[i].begin=alpha[w]+1;
ostov[i].end=w+1;
ostov[i].len=g.a[alpha[w]][w];
// цикл корректировки значений во вспомогательных
// массивах – вершина w может оказаться ближайшей
// из каркаса для еще невключенных вершин
for(v=0;v<g.n;v++)
{
flag=0;
for(ii=0;ii<count; ii++)
if(nodes[ii]==v)
flag=1;
if(flag==0 && g.a[w][v]!=MAX_INT)
if(beta[v]>g.a[w][v])
{
alpha[v]=w;
beta[v]=g.a[v][w];
131
 .       Практикум по курсу «Алгоритмизация и программирование». Часть 2
     {
         // если v не смежна нулевой вершине
         alpha[v]=-1;
         beta[v]=MAX_INT;
     }
for(i=0;i в каркас
     ostov[i].begin=alpha[w]+1;
     ostov[i].end=w+1;
     ostov[i].len=g.a[alpha[w]][w];
     // цикл корректировки значений во вспомогательных
     // массивах – вершина w может оказаться ближайшей
     // из каркаса для еще невключенных вершин
     for(v=0;vg.a[w][v])
               {
                    alpha[v]=w;
                    beta[v]=g.a[v][w];

                          131

Страницы