writeln('Отсортировать вершины по неубыванию?');

writeln(' 1-ДА');

writeln(' 2-НЕТ');

sormen:=readkey;

if sormen='1' then begin

Sort;

sor:=true;

end;

end;

prosm:=false;

write('Что будем искать : ');

readln(key); writeln;

start(t);

kols:=0;

for fil:=1 to 10000 do

begin

schet:=0;

find:=false;

Write_S(key,prosm,find,schet); {поиск в ширину}

kols:=kols+schet;

end;

stop(t);

if not(find) then write('К сожалению такой вершины нет .')

else begin

writeln('Вершина графа ',ver[p],' найдена!');

writeln('Количество сравнений: ',kols/10000:5:1);

report('Время поиска вершины',t);

end;

readkey;

end;

end;

end;

end.

4.2 Контрольный пример для тестирования №1.

Количество вершин графа – 5, ребра между ними формируются случайным образом.

Список инцидентности созданного графа:

74 497-174-§

174 §

55 497-§

497 §

661 497-§

КОЛ-ВО РЕБЕР СОЗДАННОГО ГРАФА: 4

Содержание информационных вершин: 74 174 55 497 661

Примечание: символ «§» соответствует концу списка (nil).

Полученный граф изображен на рис.6

55 74

497

661 174

рис. 6

4.3 Контрольный пример для тестирования №2.

Количество вершин графа – 7, ребра между ними формируются случайным образом.

Список инцидентности созданного графа:

704 66-373-434-§

434 373-§

766 706-373-434-§

373 66-§

66 §

706 66-704-§

454 706-66-373-§

КОЛ-ВО РЕБЕР СОЗДАННОГО ГРАФА: 13

Содержание информационных вершин: 704 434 766 373 66 706 454

Примечание: символ «§» соответствует концу списка (nil).

Полученный граф изображен на рис.7

704

454 66

373 434

706 766

рис. 7

4.4 Руководство пользователя.

При запуске программы на экране появляется основное меню программы, которое состоит из четырех пунктов:

1 Создание графа

2 Просмотр графа

3 Поиск элемента графа

4 Выход.

Выбор интересующего пункта осуществляется с помощью клавиш «1», «2», «3» и «4».

а) «Создание графа»

Выбрав пункт «Создание графа», на экране появится меню выбора количества вершин графа: 10, 100, 400 и другое.

Нажав клавишу с порядковым номером пункта меню, Вы выберете необходимое количество вершин. Далее, нажав клавишу 1 Вы разрешите программе вывести на экран список инцидентности графа, а нажав 0 – запретите.

б) «Просмотр графа»

При выборе пункта «Просмотр графа», на экране появится список информационных вершин созданного графа.

в) «Поиск элемента графа»

При выборе пункта «Поиск элемента графа» на экране сначала появляется запрос на сортировку информационных вершин. Затем Вам предстоит задать элемент поиска в графе, после чего при удачном поиске на экран будет выведено время поиска и среднее количество сравнений. Время поиска вычисляется с помощью процедур Start,Stop и Report, описанных в модуле Newtimer. Листинг модуля Newtimer описан в Приложении А.

г) «Выход»

При выборе пункта «Выход» программа прекращает свою работу.

5. Результаты тестирования

Исследуем результаты работы программы, для чего сначала измерим время поиска для трех графов из 100, 200 и 400 элементов, отсортированных в порядке возрастания и не отсортированных и сравним полученные результаты.

Количество информационных вершин – 10, вершины не отсортированы, их содержание:

97 920 635 286 590 938 981 716 427 474

Что будем искать : 427

Вершина графа 427 найдена!

Количество сравнений: 9.0

Момент запуска: 23:53:46.50

Момент остановки: 23:53:46.66

Время поиска вершины : 0.00001 cek.

Количество информационных вершин – 10, вершины отсортированы, их содержание:

32 192 234 243 297 324 775 804 982 986

Что будем искать : 192

Вершина графа 192 найдена!

Количество сравнений: 2.0

Момент запуска: 23:55:28.33

Момент остановки: 23:55:28.44

Время поиска вершины : 0.00001 cek.

Количество информационных вершин – 100, вершины не отсортированы, их содержание:

575 128 905 777 923 75 716 446 477 627 70 591 250 555 111 208 315 417 309 723 963 250 561 966 790 982 965 446 228 1 344 446 237 552 912 756 142 875 665 83 863 265 369 427 0 476 253 987 537 135 768 374 117 86 12 204 149 849 694 332 219 600 738 310 532 358 882 844 394 285 899 302 940 293 276 569 607 350 478 806 95 190 153 891 774 322 876 605 798 525 310 851 399 246 876 464 91 567 308 386

Что будем искать : 293

Вершина графа 293 найдена!

Количество сравнений: 74.0

Момент запуска: 23:58:09.98

Момент остановки: 23:58:11.08