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

fscanf (in,"%c",&g);

while (g!='-')                                                                           // считываем начало дуги до

{ m->next=new name;                                       // символа «-» в список посимвольно

m=m->next;

m->sim=g;

fscanf (in,"%c",&g);

}

m->next=NULL;

place1=Search(head,beg); // определяем порядковый номер вершины – начала дуги

beg=new name;

m=beg;

fscanf (in,"%c",&g);

while (g!='\n' && !feof(in) )                                                    // считываем конец дуги до

{ m->next=new name;                                // до конца строки, либо до конца файла

m=m->next;

m->sim=g;

fscanf (in,"%c",&g);

}

m->next=NULL;

place2=Search(head,beg); // определяем порядковый номер вершины – начала дуги

matrix1[place1][place2]=1; // делаем элемент матрицы дуг в строчке = порядковый

}                                              // номер начало дуги, в столбце = порядковый номер

}                                                      // конца дуги равным 1

void InputSD (stack * & SD, int elem)                               // функция помещения элемента в стек

{ stack *k;

k=SD;                                           // запоминается указатель на голову стека в голове стека SD=new stack;                // создаётся новая ячейка указатель next новой ячейки делаем

SD->next=k;                                                     // указывающим на следующий элемент стека

SD->sim=elem;                                          // заполняем информационное поле головы стека

}

int TakeSD (stack * & SD)                                                     //функция взятия элемента из стека

{ stack *k; int elem;

elem=SD->sim;                                                                                            //берётся элемент

k=SD;                                                                              // делается указатель на голову стека

SD=SD->next;                                                                                           // меняем голову стека

delete k;                                                                                                  // удаляем старую голову

return elem;                                                                             // возвращается взятый элемент

}

char CleanSD (stack * SD)                                                 // функция проверки стека на пустоту

{ if (SD==NULL) return 0; else                                        //если стек пуст возвращаем 0, иначе 1

return 1;

}

void MatBuild (int i, char **matrix1,char **matrix2,int number) // функция определения

{ stack *SD=NULL; int j,l=i; char m=1,q;                // доступных путей для вершины графа

matrix2[l][l]=1;        // делаем диагональные элемент матрицы в проверяемой строчке = 1

InputSD(SD,i);                                     //помещаем пор. номер проверяемой вершины в стек

while (m)                                                                                                       // пока стек не пуст

{ j=0; q=1;

do    //поиск неисследованного пути в строке, пока не найден или не конец строки

{ if (matrix1[i][j])                                        //если элемент в строке = 1, а в матрице-

{ if (!matrix2[l][j]) q=0;           // путей это ещё нет, то выход из поиска пути

else j++;                                 //иначе проверка следующей ячейке в строке

}              

}

while (q && j!=number);

if(j==number)                                   // если конец строки, то забираем элемент из стека

{ i=TakeSD(SD);                                  // если стек не пуст, то смотрим элемент в его

if(CleanSD(SD)) i=SD->sim; else m=0;// голове и продолжаем поиск нового пути

}                                     // с него, иначе выход из определения путей для вершины

else                          // иначе начинаем поиск дальнейшего пути, для новой вершины.

{ i=j;                          // Помещаем её номер в стек. Делаем элемент матрицы дуг с