Поиск в ширину на графах
mg:=readkey;
if mg='1' then mgsi:=true
else mgsi:=false;
clrscr;
mark(size);
Make_Graph(mgsi);
mem:=true;{теперь память можно освобождать}
sor:=false; {вершины не отсортированы}
readkey;
end;
'2': begin {Просмотр графа }
textmode(2);
textbackground(blue);
clrscr; textcolor(lightgreen);
gotoxy(32,3); Writeln('Просмотр графа:');
key:=-1;
find:=false;
prosm:=true; schet:=0;
Write_S(key,prosm,find,schet); writeln;
readkey;
end;
'3': begin {Поиск элемента графа}
clrscr; textcolor(lightgreen);
if not(sor) then begin
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
5
5
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
3
73
434
7
06
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
Время поиска вершины : 0.00010 cek.
Количество информационных вершин – 100, вершины отсортированы, их содержание:
0 1 12 70 75 83 86 91 95 111 117 128 135 142 149 153 190 204 208 219 228 237 246 250 250 253 265 276 285 293 302 308 309 310 310 315 322 332 344 350 358 369 374 386 394 399 417 427 446 446 446 464 476 477 478 525 532 537 552 555 561 567 569 575 591 600 605 607 627 665 694 716 723 738 756 768 774 777 790 798 806 844 849 851 863 875 876 876 882 891 899 905 912 923 940 963 965 966 982 987
Что будем искать : 293
Вершина графа 293 найдена!
Количество сравнений: 30.0
Момент запуска: 23:59:08.14
Момент остановки: 23:59:08.80
Время поиска вершины : 0.00006 cek.
Количество информационных вершин – 400, вершины не отсортированы, их содержание:
963 663 915 353 650 103 540 531 548 338 960 515 143 963 765 42 822 188 102 85 361 193 137 582 756 241 325 234 400 482 104 416 826 611 874 500 505 805 365 134 436 606 755 278 513 684 151 42 895 633 291 621 873 249 566 877 965 925 747 359 220 126 991 823 970 79 18 524 513 127 551 851 462 403 375 88 739 754 645 357 457 82 274 23 171 523 537 131 227 148 231 657 201 88