Поиск минимального подмножества вершин заданного орграфа, от которых достижимы все остальные его вершины, страница 5

InputSD(SD,i);                  // номером строки = изначально проверяема вершина,

matrix2[l][i]=1;                                        // номером столбца = найденная вершина

}

}

}

char Program (int *buf, int number, int i, char **matrix2)  // функция создания и заполнения

{ char resh=1; char *m; int j,l;                                        // массива доступных путей подмножества

m=(char*)malloc(number*sizeof(char));                             // для элементов из массива вариантов

for(j=0; j!=number ;j++) m[j]=0;           // создание и обнуление массива под доступные пути

for(j=0; j!=i+1;j++) for(l=0; l!=number ;l++) if (matrix2[buf[j]][l]) m[l]=1;               // заполнение

for(l=0; l!=number ;l++) if (m[l]==0) resh=0;               // массива доступных путей: берётся return resh;                                  // вершина из варианта и если в её ячейке есть 1, то

}                                                   // соответствующая ячейка массива доступных путей

                                                     // приравнивается 1, затем проверяется созданный

                                                     // массив. Если среди его элементов нет 0, то решение

                                                     // найдено.

// возвращаем 1, если решение найдено, иначе 0

void Perebor (int * & buf, int q, int number, int i)           // функция изменяющая массив buf –

{ int t;                                                         // массив-вариант-вершин на следующий вариант

buf[q]++;                  // увеличиваем на единицу элемент под нужной позицией, заполняем for(t=q+1; t<i+1 ; t++) buf[t]=buf[q]+t-q;            // все последующие элементу согласно методу

if (buf[q]>number+q-i-1) { q--; Perebor(buf,q,number,i); }                 // решения. Если элемент

}                                       // превысил вычисляемое по формуле максимальное значение,

                                         // то переключаем изменяемую позицию на предыдущую и

                                         // запускаем функцию ещё раз

void Output (int *buf, FILE *out, list *head, int i)                      // функция вывода в файл имён

{ int j=0,v=0; list *p; name *q;                                   // вершин, которые записаны в массиве buf

p=head->next;                             // делаем указатель на элемент, следующий после головы,

while(v!=i+1)                              // в списке с наименованиями вершин

{ if (buf[v]==j)                      // пока не закончились вершины в массиве-варианте

{ q=p->sim;                  // вершин делаем если порядковый номер вершины не

do                               // совпадает с номером вершины в массиве-варианте, то

{ q=q->next;                                // переходим на следующую вершину, иначе

fprintf (out,"%c",q->sim);        // выводим наименование вершины, ставим

}                                                   // в конце запятую, переключаемся на

while(q->next!=NULL);                   // следующую вершину в массиве-варианте

fprintf (out,",");

v++;

}

j++;

p=p->next;                                      // переключаемся на следующее наименование

}

}

char Zadacha (char **matrix2,int i, int number, list *head, FILE *out)         // функция анализа

{ char resh=0; int j,q=i; int *buf;                                                                                // матрицы-путей

buf=(int*)malloc((i+1)*sizeof(int));           //создание массива под вариант-вершин-решения

for(j=0;j!=i+1;j++) buf[j]=j;                   //заполнение массива-варианта первым вариантом

resh=Program(buf,number,i,matrix2);                                                            // проверка варианта

for(j=number-i-1; buf[0]!=j && !resh ;)                       // цикл проверок, пока первый элемент

{ Perebor(buf,q,number,i);                    // варианта не равен высчитанному по формуле и

q=i;                                                          // не найдено решение, берётся новый вариант.