Поиск в ширину на графах

textcolor(white);gotoxy(5,5);

writeln('* Исследование поиска в ширину *');

textcolor(black); gotoxy(7,22);

writeln('Created by Andrew Spikhailo');

gotoxy(15,24); write('ARMAVIR 2001');

textcolor(white);

gotoxy(7,10); write('+-----------MENU-----------?');

gotoxy(7,11); write('|');textcolor(green);

write('1 Создание графа ');

textcolor(white);write('|');

gotoxy(7,12); write('|');textcolor(green);

write('2 Просмотр графа ');

textcolor(white);write('|');

gotoxy(7,13); write('|');textcolor(green);

write('3 Поиск элемента графа ');

textcolor(white);write('|');

gotoxy(7,14); write('|');textcolor(green);

write('4 Выход ');

textcolor(white);write('|');

gotoxy(7,15); write('|');textcolor(white+128);

write('Выберите номер пункта меню'); textcolor(white);write('|');

gotoxy(7,16); write('?--------------------------+');

menu:=readkey;

case menu of

'1': begin

{освобождение памяти, если она была занята}

textmode(2);

textbackground(blue);

clrscr; textcolor(lightgreen);

if mem then release(size);

repeat

clrscr;

write('Число вершин графа: ');

writeln('(1) - десять');

gotoxy(21,wherey);

writeln('(2) - сто');

gotoxy(21,wherey);

writeln('(3) - четыреста');

gotoxy(21,wherey);

write('(4) - другое...');

raz:=0;

repeat

craz:=readkey;

case craz of

'1': raz:=10;

'2': raz:=100;

'3': raz:=400;

'4': begin

write(' ___');

gotoxy(wherex-3,wherey);

read(raz);

if (raz400) then begin

raz:=0;

gotoxy(38,wherey-1);

write('ERROR...');

delay(1000);

end;

end;

end;

until (craz='1') or (craz='2') or (craz='3') or (craz='4');

clrscr;

until raz>0;

writeln;

write('вывод списка инцидентности графа: ');

writeln('0 - запретить');

gotoxy(35,wherey);

write('1 - разрешить');

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

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

Время поиска вершины : 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 12

620 660 273 759 359 725 191 88 517 178 361 361 527 92 412 803 656 220 967

597 889 625 740 50 219 289 519 202 120 687 957 483 263 554 353 273 769 330

825 486 546 26 566 520 501 487 96 201 682 288 677 570 647 745 329 619 594

787 100 348 70 661 523 736 286 699 434 505 345 659 558 767 930 339 559 923

246 477 449 428 262 152 551 269 552 182 421 277 286 252 408 624 157 746 782

119 302 534 581 163 506 184 622 470 239 341 330 908 326 255 318 89 294 696

884 536 687 729 849 570 903 100 412 251 359 207 930 994 3 888 816 722 499

517 955 649 619 145 328 80 633 657 752 805 761 195 920 978 963 318 152 560

634 643 533 715 982 950 369 742 156 980 111 421 401 411 194 876 797 756

449 306 387 158 3 213 719 314 861 968 122 21 570 826 242 79 648 768 660

520 702 755 610 420 391 267 114 759 683 235 77 71 46 722 136 875 526 966

306 108 858 644 729 54 46 460 71 499 85 428 356 103 737 445 289 210 538 31

371 595 466 328 342 874 924 727 757 563 981 730 734 23 18 911 181 769 228

73 43 886 626 977 359 527 483 236 196 741 382 250 731 95 291 273 51 843 342

988 453 621 228 190 296 897 399 438 703 663 466 789 656 110 504 964 289 260

154 570 413 796 709

226 583 573 611 701 244 544 10 436 759 86 333 44 364

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

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

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

Момент запуска: 00:03:13.99

Момент остановки: 00:03:18.83

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

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

содержание:

3 3 10 12 18 18 21 23 23 26 31 42 42 43 44 46 46 50 51 54 70 71 71 73 77 79

79

80 82 85 85 86 88 88 88 89 92 95 96 100 100 102 103 103 104 108 110 111 114

119 120 122 126 127 131 134 136 137 143 145 148 151 152 152 154 156 157 158

163 171 178 181 182 184 188 190 191 193 194 195 196 201 201 202 207 210 213

219 220 220 226 227 228 229 231 234 235 236 239 241 242 244 246 249 250 251

252 255 260 262 263 267 269 273 273 273 274 277 278 286 286 288 289 289 289

291 291 294 296 302 306 306 314 318 318 325 326 328 328 329 330 330 333 338

339 341 342 342 345 348 353 353 356 357 359 359 359 359 361 361 361 364 365

369 371 375 382 387 391 399 400 401 403 408 411 412 412 413 416 420 421 421

428 428 434 436 436 438 445 449 449 453 457 460 462 466 466 470 477 482 483

483 486 487 499 499 500 501 504 505 505 506 513 513 515 517 517 519 520 520

523 523 524 526 527 527 531 533 534 536 537 538 540 544 546 548 551 551 552

554 558 559 560 563 566 566 570 570 570 570 573 581 582 583 594 595 597 606

610 611 611 619 619 620 621 621 622 624 625 626 633 633 634 643 644 645 647

648 649 650 656 656 657 657 659 660 660 661 663 663 677 682 683 684 687 687

696 699 701 702 703 709 715 719 722 722 725 727 729 729 730 731 734 736 737

739 740 741 742 745 746 747 752 754 755 755 756 756 757 759 759 759 761 765

767 768 769 769 782 787 789 796 797 803 805 805 816 822 823 825 826 826 843

849 851 858 861 873 874 874 875 876 877 884 886 888 889 895 897 903 908 911

915 920 923 924 925 930 930 950 955 957 960 963 963 963 964 965 966 967 968

970 977 978 980 981 982 988 991 994

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

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

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

Момент запуска: 00:04:21.33

Момент остановки: 00:04:23.58

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

Как показал эксперимент, сортировка информационных вершин графа влияет

на время поиска элемента методом просмотра в ширину в графе. Уменьшается

количество сравнений, что также повышает быстродействие алгоритма. Однако

это существенно повышает эффективность алгоритма только при намного большем

количестве вершин, чем в произведенных опытах.

Время поиска даже при максимально возможном количестве вершин (400)

настолько мало, что засечь его не представляется возможным. Поэтому процесс

поиска повторяется 10000 раз. Точное время вычисляется в подключенном

модуле Newtimer по формуле:

T=Q/n ,где

Q- общее время поиска;

n – количество циклов поиска (10000).

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

небольшой размерности, но если графы будут размерности более чем 1 миллиард

вершин, то время будет ощутимо. И можно получить выгоду из алгоритма поиска

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

элементов, а не несколько раз, но используя немного элементов.

Таким образом, алгоритм поиска в ширину в графе является достаточно

эффективным и может использоваться в программах для быстрого поиска

элементов.

Заключение

Современное состояние и тенденции развития вычислительной техники как

основного инструмента информатики таковы, что наряду с увеличением

функциональности вычислительная техника приобретает свойства, позволяющие

работать на ней пользователю, не разбирающемуся в программировании. В этот

период появился более качественный интерфейс программ. Появились структуры

графических данных и более крупные, интегральные информационные единицы –

объекты. Следствием стало бурное развитие объектно-ориентированных систем

программирования, таких как Visual C++, Visual BASIC и других, в основе

которых лежит обработка объектных структур данных. Также появились новые

языки программирования ADA, OCCAM.([3]) И если раньше большой популярностью

пользовались простые линейные алгоритмы то в настоящее время алгоритмы

таких типов как деревья, графы, списки, очереди – получают все большее

распространение.

Данный алгоритм может найти своё применение в программах для

транспортных и коммуникационных сетей, таких как: железнодорожной

транспортной сети, где вершины - станции, связи – дороги, таксомоторная

сеть: вершины – места стоянки автомобилей, связи – пути подъезда;

перемещение потока вещества по системе труб в определенный пункт назначения

и т.д. На основе алгоритма поиска в ширину в графе можно построить

программу вывода дерева наименьшей стоимости, что позволит рассчитывать

кратчайшие пути к определенному месту назначения (вершине).

Таким образом, развитие информационных технологий, их проникновение во

все области жизнедеятельности человека требуют компьютерного отображения

информации в виде соответствующих структур данных. И графы, являясь одной

из частей этих структур данных, играют важную роль в современном

программировании, графы встречаются в сотнях разных задач.

Список литературы:

1. Вирт Н. Алгоритмы и структуры данных.– М.: Мир, 1989.

2. Кнут Д. Искусство программирования для ЭВМ. – В 7 т. - М.: Мир,

1876.

3. Лойко В.И. Структуры и алгоритмы данных ЭВМ: Курс лекций для спец.

220400 – Краснодар: КубГТУ, 1998.

4. Марченко А.И., «Программирование в среде «Turbo Pascal 7.0»,

«Век+», Киев 1999 г.

Подпись_________________________Дата___________________________

Приложение А

Листинг модуля Newtimer

unit newtimer;

interface

procedure start(var x: longint); {определяет время начала работы}

procedure stop(var x: longint); {определяет время окончания работы}

procedure format(hour, min, sec, hund: word);

procedure Report(Msg:string; x:longint);

implementation

uses dos;

var

hour_start, min_start, sec_start, hund_start,

hour_stop, min_stop, sec_stop, hund_stop,

hour, min, sec, hund: word;

systimer : longint absolute $0040 : $006c;

procedure start;

begin

gettime(hour_start, min_start, sec_start, hund_start);

x:=systimer;

while x=systimer do; {ожиание момента изменения таймера}

x:=systimer;

end;

procedure stop;

begin

gettime(hour_stop, min_stop, sec_stop, hund_stop);

x:=systimer-x;

end;

procedure format;

procedure print(w: word);

begin

if w<10 then write('0');

write(w);

end;

begin

print(hour); write(':');

print(min); write(':');

print(sec); write('.');

print(hund);

writeln;

end;

procedure Report;

{Вывод на печать измеренного интервала в секундах и

сообщения через переменную Msg}

begin

write('Момент запуска: ');

format(hour_start, min_start, sec_start, hund_start);

write('Момент остановки: ');

format(hour_stop, min_stop, sec_stop, hund_stop);

writeln(msg,' : ',x/182000:5:5,' cek.');

end; end.

-----------------------

(б)

1(1)

10(7)

Страницы: 1, 2