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

resh=Program(buf,number,i,matrix2);              // Изменяемая позиция переключается на

}                                                                                          //последнюю. Проверка варианта

if (resh) Output(buf,out,head,i);                                    //если найдено решение, то выводим его

return resh;                    //возвращается счётчик = 1, если решение найдено и = 0, если нет

}

void main ()

{ FILE *in,*out; int number,i,q,t,j,* buf; char **matrix1,**matrix2,resh;

if((in=fopen("D:\input.txt","r"))==NULL)

{perror("Mistake"); exit(0);}

out=fopen("D:\output.txt","w");

list *head=new list;

number=InputVer(head,in);               // ввод названий вершин и определение их количества

matrix1=(char**)malloc(number*sizeof(char*));               //создание массива под матрицу-дуг for(i=0; i!=number ;i++) matrix1[i]=(char*)malloc(number*sizeof(char));         // и его обнуление

for(i=0; i!=number ;i++) for(j=0; j!=number ;j++) matrix1[i][j]=0;

InputDug(head,in,matrix1);                                             //определение элементов матрицы-дуг

fclose(in);

matrix2=(char**)malloc(number*sizeof(char*));          //создание массива под матрицу-путей

for(i=0; i!=number ;i++) matrix2[i]=(char*)malloc(number*sizeof(char));             //и его обнуление

for(i=0; i!=number ;i++) for(j=0; j!=number ;j++) matrix2[i][j]=0;

for(i=0; i!=number ;i++) MatBuild(i,matrix1,matrix2,number);   //цикл определения элементов

resh=0;                                                                                               //матрицы-путей построчно

for(i=0; i!=number-1 && !resh ;i++) resh=Zadacha(matrix2,i,number,head,out);  // цикл анализаif (!resh)                  //матрицы-путей, с изменяемым количеством вершин в подмножестве-

{ buf=(int*)malloc(number*sizeof(int));              // варианте. Продолжается, пока не найдено

for(j=0; j!=number ;j++) buf[j]=j;     // решение или не перебраны все варианты количества

Output(buf,out,head,number-1); // вершин в подмножестве-варианте, кроме варианта – все

}                                   // вершины. Если решение не найдено, то создаём вариант-вершин,

fclose(out);                                                           // состоящий из всех вершин, и выводим его.

}

  7. Набор тестов

№	Дано	Графическое представление	Результат	Примечание
1	One		One,	Граф, состоящий из 1 вершины.
2	One,Two		One,Two	Граф, состоящий из 2 не связанных дугой вершин. Решение – все вершины.
3	One,Two,Three ,Four,Five		One,Two,Three, Four,Five,	Граф состоящий из произвольного количества вершин без дуг. Решение – все вершины.
4	One,Two\n One-Two		One,	Граф, состоящий из 2 вершин. Одна, связана с другой дугой.
5	One,Two\n One-Two\n Two-One		One,	Граф, состоящий из 2 обоюдно связанных между собой дугами вершин. Решение – 1ое найденное.
6	One,Two,Three ,Four,Five\n Four-Three\n Three-Two\n Five-One		Four,	Граф, состоящий из произвольного количества вершин с вершиной, из которой есть путь во все остальные.
7	One,Two,Three ,Four,Five\n One-Two\n Three-Four		One,Three,Five	Граф, состоящий из произвольного количества вершин, где решение – подмножество, с количеством вершин больше 1 и меньше общего количества.
8	One1,Two2,T ,Four L,Five\n One1-Two2\n T-Four L\n	Граф из предыдущего теста (изменены названия вершин)	One1,T,5	Проверка работоспособности Вершин с названиями: ·  содержащими цифры и буквы ·  состоящими из одного символа ·  состоящими из цифры

8. Результаты работы программы

Программа работает верно, что подтверждено тестами.