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

4.Алгоритм решения задачи

{

Создать пустой список-наименования-вершин;

Ввод вершин;

Создать обнулённую матрицу-дуг размером количество-вершин на количество-вершин;

Заполнить матрицу-дуг дугами;

Создать обнулённую матрицу-путей размером количество-вершин на количество-вершин;

Решение=0;

При количество вершин=1

            Решение = Задача (количество вершин, матрица-путей );

            Количество вершин = количество вершин+1;

Пока количество вершин < общего количества вершин -1 и не найдено решение;

Если Решение = 0, то Вывод всех вершин;

}

Алгоритм функции Задача (количество вершин, матрица-путей)

{

делать

            Создать следующий вариант буфер-вариант-вершин.

            Решение = Проверка (буфер-вариант-вершин, матрица путей);

пока не закончились варианты буфера и не найдено решение

Если Решение=1, то Вывод вершин, записанных в буфер-вариант вершин;

Вернуть Решение;

}

Алгоритм функции Проверка (буфер-вариант-вершин, матрица-путей)

{

Создать обнулённый одномерный массив размером количество вершин;

Если для вершины из буфера-вариат-вершин элемент равен 1, то делаем элемент массива равным 1.

Если в массиве хоть один элемент равен 0, то возвращаем 0, иначе 1.

}

Алгоритм функции создания буфер-вариант-вершин(изменяемая позиция, буфер-вариант вершин, количество вершин в графе, количество вершин в варианте)

{

Увеличиваем на единицу элемент под нужной позицией;

Заполняем все последующие элементы согласно методу решения.

Если элемент превысил вычисляемое по формуле максимальное значение (количество элементов + изменяемая позиция - количество вершин в варианте), то

Изменяемая позиция = изменяемая позиция – 1;

Запускаем функция создания буфер-вариант-вершин;

}

Примечание – всегда при первоначальном запуске функции изменяемая позиция равна количеству вершин в варианте

5. Структура программы

 

int InputVer(list *head,FILE *in) – функция ввода названий вершин графа в список; list *head – указатель на список; FILE *in – указатель на поток – входной файл.

return number – возвращает количество вершин в графе. Number    [0;+      )

void InputDug(list *head,FILE *in,char **matrix1) – функция ввода дуг графа в матрицу matrix1 (матрица дуг); list *head – указатель на список с элементами – название вершины графа; FILE *in – указатель на поток – входной файл; char **matrix1 – указатель на двумерный массив определяющий граф. Элемент матрицы типа char   { 0 ; 1 }.

int Search(list *head,name *beg) – функция поиска слова, находящегося посимвольно в списке (*beg – указатель на голову этого списка) в списке с элементами (*head – указатель на голову этого списка) – список с наименованием вершины графа посимвольно.

return place – возвращает номер позиции, на которой это слово находится в списке списков слов, если первая позиция – 0.

void InputSD(stack * & SD,int elem) – функция помещения элемента в стек. Видоизменённый стек возвращается не явно; stack * & SD – стек.int elem – помещаемый элемент. elem   [0; +     )

int TakeSD(stack * & SD) – функция взятия элемента из стека. Видоизменённый стек возвращается не явно. stack * & SD – стек.

return elem – возвращает элемент - элемент взятый из стека типа int. elem           [0; +       ).

char CleanSD(stack * SD) – функцияпроверки стека на пустоту. stack * SD – указатель на стек.

,возвращает 0, если стек пуст и 1, если стек не пуст.

void MatBuild(int i,char **matrix1,char **matrix2,int number) – функция определения доступных путей для вершины графа под номером i из матрицы-дуг. i       [0; +      ); char **matrix1 – указатель на матрицу-дуг; char **matrix2 – указатель на матрицу-путей. Элемент матрицы типа char    { 0 ; 1 }; int number - количество вершин в графе. Number  [0;+   )

char Program(int *buf,int number,int i,char **matrix2) – функция создания и заполнения массива доступных путей для элементов, номера которых берутся из массива buf; int *buf – указатель на массив-вариант-вершин. Его элементы – номера вершин графа типа int; int number - количество вершин в графе. Number  [0;+     ); int i – количество элементов в массиве-вариант-вершин buf. i     [0; +     ); char **matrix2 – указатель на матрицу-путей. Элемент матрицы типа char     { 0 ; 1 };