Реферат: Поиск в ширину на графах

Реферат В данной работе: 7рисунков, 1 программа, 1 приложение, 35 листов.

Ключевые слова: граф,алгоритм, поиск, ширина, программа, аргумент, элемент, массив, очередь, память,время, сравнение.

Цель работы: Исследоватьэффективность алгоритма поиска в графе в ширину.

Результат работыпрограммы: количество сравнений элемента с ключом поиска и время, за котороебыл найден элемент по данному алгоритму поиска.

Областью применениеданного алгоритма может быть разнообразна, на пример при построении картместности: вершины графа – города, связи – дороги.

СодержаниеВведение…………………………………………………………………..5стр.

1. Краткаятеория………………………………………………………..6 стр.

2. Анализалгоритма……………………………………………………11 стр.

3. Спецификациязадачи……………………………………………….14 стр.

3.1 Входные и выходныеданные…………………………………14 стр.

3.2 Используемыепроцедуры…………………………………….14 стр.

4. Программана языке Turbo Pascal..…………………………………15 стр.

4.1 Листингпрограммы…………..………….……………………15 стр.

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

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

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

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

Заключение………………………………………………………………33 стр.

Список используемой литературы……………………………………..34 стр.

Приложение А…………………………………………………………….35 стр.

Введение.

Графывстречаются в сотнях разных задач, и алгоритмы обработки графов очень важны.

Существуетмножество разработанных алгоритмов для решения различных задач из самых разныхобластей человеческой деятельности. Формулировка задачи описывает, какимтребованиям должно удовлетворять решение задачи, а алгоритм, решающий этузадачу, находит объект, этим требованиям удовлетворяющий. ([1])

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

Поиском позаданному аргументу называется алгоритм, определяющий соответствие ключа сзаданным аргументом. Алгоритм поиска в ширину может быть использован дляпросмотра созданного графа, чтобы узнать состав информационных вершин дляпоследующего поиска.

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

Если заданная информационнаявершина найдена, то происходит вывод об успешном окончании поиска, выводвремени поиска и времени поиска ключа.

1. Краткая теория.

Очевидно, чтонаиболее понятный и полезный для человека способ представления графа— изображение графа на плоскости в виде точек и соединяющихих линий — будет совершенно бесполезным, если мы захотим решать с помощью ЭВМзадачи, связанные с графами. Выбор соответствующей структуры данных дляпредставления графов имеет принципиальное влияние на эффективностьалгоритмов, поэтому мы подробнее остановимся на этой проблеме. Мыпокажем несколько различных способов представления и краткоразберем их основные достоинства и недостатки.

Мыбудем рассматривать как ориентированные, так и неориентированныеграфы. Граф мы будем всегда обозначать G = (V,E), где V обозначает множествовершин, а Е — множество ребер, причем Е Í V X V для ориентированного графа и ЕÍ{{х, у}: х, у Î V ۸ х¹у}для неориентированного графа. Будем также использовать обозначения |V| = n и |Е| = m.

Втеории графов классическим способом представления графа служит матрицаинциденций. Это матрица А с n строками, соответствующимивершинам, и m столбцами, соответствующимиребрам. Для ориентированного графа столбец, соответствующий дуге<x, y> Î E, содержит —1 в строке, соответствующей вершине х, 1 встроке, соответствующей вершине у, и нули во всех остальных строках (петлю, т.е. дугу вида <x, x>,удобно представлятьиным значением в строке х, например, 2).В случае неориентированного графа столбец,соответствующий ребру {х, у},содержит 1 в строках, соответствующих х и у, и нули в остальных строках. Это проиллюстрировано на рис. 2.1. С алгоритмическойточки зрения матрица инциденций является, вероятно, самым худшим способом представления графа, который только можно себе представить. Во-первых, онтребует nm ячеек памяти,причем большинство этих ячеек вообще занято нулями. Неудобентакже доступ к информации. Ответ на элементарные вопросы типа «существуетли дуга <x,y>?»,«к каким вершинам ведут ребра из х?» требует в худшем случаеперебора всех столбцов матрицы, а следовательно, m шагов.

Лучшим способом представления графа является матрица смежности, определяемая как матрица В = [b•j]размера nхm,

<1,2>

<1,3>

<3,2>

<3,4>

<5,4>

<5,6>

<6,5>

(а)/>/>/>/> 1 –1 –1 0 0 0 0 0

/> 2 1 0 1 0 0 0 0

3 0 1 -1 -1 0 0 0

4 0 0 0 1 1 0 0

5 0 0 0 0 -1 -1 1

6 0 0 0 0 0 1 -1

/> /> /> /> /> /> /> /> />

{1,2}

{1,3}

{1,5}

{2,3}

{2,5}

{3,4}

{4,5}

{4,6}

{5,6}

/>/>(б)/>/>/> 1 1 1 1 0 0 0 0 0 0

2 1 0 0 1 1 0 0 0 0

3 0 1 0 1 0 1 0 0 0

4 0 0 0 0 0 1 1 1 0

5 0 0 1 0 1 0 1 0 1

6 0 0 0 0 0 0 0 1 1

/>/>

Рис. 1. а) Ориентированный граф и его матрица инциденций;

б) Неориентированный граф и егоматрица инциденций.

где bij =1, если существует ребро, идущее из вершины х в вершину у, и bij = 0 в противном случае. Здесь мыподразумеваем, что ребро {х, у} неориентированного графа идет как от х к у, так иот у к х, так что матрица смежности такого графа всегда является симметричной. Это проиллюстрировано на рис. 2.

Основнымпреимуществом матрицы смежности является тот факт, что за один шаг можно получить ответна вопрос «существует ли ребро из х в y?». Недостатком жеявляется тот факт, что независимо от числа ребер объем занятой памяти составляет n2.На практике это неудобство можно иногда уменьшить, храня целуюстроку (столбец) матрицы в одном машинном слове — этовозможно для малых n.

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

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

ПустьР — некоторое свойство графа P(G) = 0 или P(G)=1 в зависимости от того,обладает или не обладает G нашим свойством. Предположим, что свойство Р удовлетворяет следующим трем условиям:

(а) P(G)=P(G'), если графы G и G' изоморфны;

(б) P(G) =0 для произвольного пустого графа <V,Æ> и P(G)=1 для произвольногополного графа <V, P2(V)>с достаточно большим числом вершин;

1 2 3 4 5 6 1 2 3 4 5 6

/>/>/>/>/>/>/>/> 1 0 1 1 0 0 0 1 0 1 1 0 1 0

2 0 0 0 0 0 0 2 1 0 1 0 1 0

3 0 1 0 1 0 0 3 1 1 0 1 0 0

4 0 0 0 0 0 0 4 0 0 1 0 1 1

5 0 0 0 1 0 1 5 1 1 0 1 0 1

6 0 0 0 0 1 0 6 0 0 0 1 1 0

/>/>/>/>

Рис. 2. Матрицы инциденций для графов на рис.1.

(в) добавление ребра ненарушает свойства Р, т. е. P(G)<P(G') для произвольных графов G=(F,E) и G'=(V, E'), таких что Е = Е'.

Примеромтакого свойства Р является существование цикла (в графе, имеющем, покрайней мере три вершины).

Теорема . ЕслиР — свойство графа, отвечающее условиям (а),(б), (в), то каждый алгоритм, проверяющий свойство Р (т.е. вычисляющий значение P(G) для данного графа G) на основе матрицы смежности, выполняет в худшемслучае Ω(n2) шагов, где n— число вершин графа.

Эта теорема справедлива также для ориентированных графови для свойств, не зависящих от петель графа, т, е. отвечающих дополнительномуусловию

(г) P(G) =P(G') для произвольных ориентированных графов G = < V, E>, G’ = < V,Е> U <v, v>>, v C V.

Более экономным в отношении памяти (особенно в случае,неплотных графов, когда m гораздо меньше n2) является метод представленияграфа с помощью списка пар, соответствующих его ребрам. Пара <x, у> соответствуетдуге <х, у>, если графориентированный, и ребру {х, y} вслучае неориентированного графа(рис. 3). Очевидно, что объем памяти в этом случае составляет 2т. Неудобством являетсябольшое число шагов — порядка т вхудшем случае, — необходимое для получения множества вершин, к которымведут ребра из данной вершины.

Ситуацию можно значительно улучшить, упорядочив множествопар лексикографически и применяя двоичный поиск, нолучшим решением во многих случаях оказывается структура

1 2 1 3 1 5 2 3 2 5 3 4 4 5 4 6 5 6 1 2 1 3 3 2 3 4 5 4 5 6 6 5

Рис.3. Списки ребер соответствующиеграфам на рис.1.

данных, которую мы будем называтьсписками инцидентности. Она содержит для каждой вершины v C V список вершин и, такихчто v-> u(или v— ив случае неориентированного графа). Точнее, каждый элемент такого спискаявляется записью г, содержащей вершину г. строка и указатель г. след на следующуюзапись в списке (г. след = nil для последней записи всписке). Начало каждого списка хранится в таблице НАЧАЛО; точнее, HAЧАЛО[v] является указателем наначало списка, содержащего вершины измножества {u: v+u} ({u: v — u} для неориентированного графа). Весь такой список обычнонеформальнобудем обозначать 3AПИСЬ[v], а цикл, выполняющийопределенную операцию для каждого элемента и из этого списка в произвольной, но четко установленнойпоследовательности, соответствующей очередности элементов в списке, будемзаписывать «for u C ЗАПИСЬ [v] do ...».

Отметим,что для неориентированных графов каждое ребро {u, v}представлено дважды: через вершину v всписке ЗАПИСЬ[u] и через вершину и всписке ЗАПИСЬ[v].Во многих алгоритмах структура графадинамически модифицируется добавлением и удалением ребер. В таких случаяхполагаем, что в наших списках инцидентности элемент списка ЗАПИСЬ [u], содержащий вершину и,снабжен указателем на элемент списка 3AПИCЬ[v], содержащий вершину и,и что каждый элемент списка содержитуказатель не только к следующему элементу, но и к предыдущему. Тогдаудаляя некоторый элемент

/> <td/>

(б)

Рис.4. Списки инцидентности ЗПИСЬ[v], v=V, соответствующие графам на рис.1.

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

Аналогичнымспособом определяем для каждой вершины и неориентированного графасписок ПРЕДШ[v], содержащий вершиныиз множества (u: u -> v).

Числоячеек памяти, необходимое для представления графа спомощью списков инцидентности, будет, очевидно, иметь порядокm + n. Нарис.4 представлены списки инцидентности, соответствующие графам нарис. 1.

2. Анализ алгоритма.

Рассмотрим метод поиска вграфе, называемый поиском в ширину (англ: breadth first search). Прежде чем описать его, отметим, что при поиске в глубину чемпозднее будет посещена вершина, тем раньше она будет использована — точнее, так будет при допущении, что вторая вершина посещается перед использованием первой.Это прямое следствие того факта, что просмотренные, но еще не использованные вершины скапливаются в стеке. Поиск вширину, грубо говоря, основывается на замене стека очередью. После такой модификации, чем раньше посещается вершина(помещается в очередь), тем раньше она используется (удаляется из очереди). Использование вершины происходит спомощью просмотра сразу всех еще не просмотренных соседей этой вершины. Всяпроцедура поиска представлена ниже (данная процедура используется также и дляпросмотра графа, и в псевдокоде, описанном ниже, отсутствуют операторы, которыене используются для поиска).

1 procedure WS (v);

(*поиск в ширину в графе с началом в вершине v;

переменныеНОВЫЙ, ЗАПИСЬ — глобальные *)

2 begin

3 ОЧЕРЕДЬ := Æ; ОЧЕРЕДЬ <= v; НОВЫЙ [v]:= ложь

4 while ОЧЕРЕДЬ ¹ Æ do

5 beginр<= ОЧЕРЕДЬ; посетить р;

6 for u Î ЗАПИСЬ [р] do

7 if НОВЫЙ [u] then

8 begin ОЧЕРЕДЬ <= u; НОВЫЙ [u]:=ложь

9 end

10 end

11 end

Примечание:в 7-й строке псевдокода кромеусловия НОВЫЙ[u] должно также выполниться условие наличия связи (ребра) между v-й и u-й вершинами. Для установки наличияребра сначала в списке v-й вершины ищется информационное значение и-й вершины. Если оно найдено,то ребро установлено, если нет, то информационное значение v-й вершины ищется в списке и-йвершины, т.е. наоборот. В результате добавления двух лишних циклов поиска общийалгоритм поиска несколько теряет компактность, но на быстродействии в целом этоне сказывается.

1 procedure Write_S;

2 begin

3 for v Î V do НОВЫЙ[u]:= истина; (* инициализация *)

4 for v Î V do

5 if HOBЫЙ[v] then WG(v)

6 end

Способом, аналогичнымтому, какой был применен для поиска в глубину, можно легко показать, что вызовпроцедуры WS(v)приводит к посещению всех вершин связной компоненты графа,содержащей вершину v, причем каждая вершина просматривается в точностиодин раз. Вычислительная сложность поиска в ширину также имеет порядок О(m + n), так как каждая вершинапомещается в очередь и удаляется из очереди в точности один раз, а число итераций цикла 6, очевидно, будет иметь порядок числа ребер графа.

В очереди помещенысначала вершины, находящиеся на расстоянии 0 от v (т. е. сама вершина v), затем поочередно все новыевершины, достижимые из v, т. е. вершины, находящиеся на расстоянии 1 отv, и т. д. Под расстояниемздесь мы понимаем длину кратчайшего пути.Предположим теперь, что мы ужерассмотрели все вершины, находящиеся на расстоянии, не превосходящемr, от v, что очередь содержит всевершины, находящиеся от v нарасстоянии r, и только эти вершины. Использовав каждую вершинур, находящуюся в очереди, наша процедура просматривает некоторыеновые вершины, и каждая такая новая вершина u находится, очевидно, на расстоянии г +1 от v. После использования всех вершин из очереди, находящихсяна расстоянии r от v, она (очередь), очевидно,содержит множество вершин, находящихся на расстоянии r + 1 от v, и легко заметить, что условие индукции выполняетсяи для расстояния r +1.

На рис. 5представлен граф, вершины которого занумерованы согласноочередности, в которой они посещаются в процессе поиска в глубину.

Как и в случае поиска в глубину, процедуру WS можно использовать безвсяких модификаций и тогда, когда списки

/> /> /> /> /> /> /> /> <td/>

10(7)

Рис. 5 Нумерация вершин графа(в скобках), соответствующая очередности, вкоторой они просматриваются в процессе поиска в ширину.

инцидентности ЗАПИСЬ[v], v = V, определяют некоторый ориентированный граф. Очевидно,что тогда посещаются только те вершины, до которых существуетпуть от вершины, с которой мы начинаем поиск

3. Спецификациязадачи

3.1 Входные ивыходные данные

ver –массив вершин графа, заполняемый случайным образом целыми числами в диапазонеот 0 до 1000;

nv - массив флагов проверки вершин;

ocher –массив для организации очереди, заполняемой значениями рассматриваемыхинформационных вершин графа;

raz –переменная целочисленного типа, определяющая в программе размер создаваемогографа;

schet –счетчик количества сравнений в процедуре поиска;

key –вводимый с клавиатуры ключ поиска;

mgsi –переменная логического типа, разрешающая вывод списка инцидентности графа;

prosm — переменная логического типа, превращающая процедуру поиска WS в процедуру просмотра графа;

find — переменная логического типа, определяемая при нахождении искомой информационнойвершины;

craz, menu, mg, sormen – переменные символьного типа дляработы с меню программы.

3.2 Используемыепроцедуры

Make_Graph – процедура создания графа в динамическойпамяти;

WS — процедура просмотраграфа с v-той вершины методом поиска в ширину;

Write_S – процедура инициализации признаков просмотра вершин иуправляющая процедурой WS;

Sort — процедура сортировкивершин графа по неубыванию.

4. Текст программы на языкеTURBO PASCAL

4.1Листинг программы.

{$S+} {$R+} {$I+} {$M65520,0,655360}

program graph;

uses crt,newtimer;

const

maxraz=400;

type index=^list;

list= record

inf: word;

next: index;

end;

connection=array[1..maxraz] ofindex;

var

el,em,size: pointer;

lst,m: connection;

ver: array[1..maxraz] of word; {массиввершин}

Nw: array[1..maxraz] of boolean;

ocher: array[1..maxraz+1] ofinteger;

raz: integer;

exch,fil,i,j,l,schet,v,u,p: word;

key,kols,t,tm: longint;

mgsi,mem,sor,prosm,find:boolean;

craz,menu,mg,sormen:char;

{------------------------------------------------------

***Процедура создания графа в динамической памяти***}

procedure Make_Graph(mgsi: boolean);

label Er;

var

n: index;

i,j: word;

kolvo: longint;

spro: boolean;

begin

randomize;

for i:=1 to raz do begin

ver[i]:=random(1000);

end;

kolvo:=0;

for i:=1 to raz do begin

lst[i]:=nil;

for j:=1 to raz do begin

spro:=true;

if j=raz then goto Er;

if j=i then inc(j);

n:=nil;

n:=lst[j];

if lst[j]<>nil then

repeat

if n^.inf=ver[i] thenspro:=false;

n:=n^.next;

until (n=nil) or(not(spro));

if (round(random)=1) andspro then

begin

new(m[i]);

inc(kolvo);

m[i]^.inf:=ver[j];

m[i]^.next:=lst[i];

lst[i]:=m[i];

end;

Er:

end;

writeln;

if mgsi then {ВЫВОДСВЯЗЕЙВЕРШИН}

for i:=1 to raz do {}

begin {}

write(ver[i],'-'); {}

m[i]:=lst[i]; {}

if m[i]<>nilthen {}

repeat {}

write(m[i]^.inf,'═'); {}

m[i]:=m[i]^.next; {}

untilm[i]=nil; {}

writeln(''); writeln; {}

end; {}

writeln('КОЛ-ВО РЕБЕР СОЗДАННОГО ГРАФА: ',kolvo);

end;

{------------------------------------------------------

***Процедура просмотра графа с v-той вершины методом поиска вширину***}

Procedure WS(v:word; var find:boolean;

varschet: word);

var {v — пор. номер вершины графа}

ik,oo,o9,o3,op: integer;

rebro: boolean;

begin {оо — размер очереди в данном цикле}

ocher[1]:=v; oo:=1; {вставка текущего индекса вершины вначало очереди}

Nw[v]:=False; {флаг на вершину текущего индекса}

while oo>0 do begin {пока есть очередь...}

p:=ocher[1];{удаление 1-го элемента из очереди иприсваивание его p}

for op:=1 to oo-1 do ocher[op]:=ocher[op+1]; ocher[oo]:=0;

dec(oo);

inc(schet); {счетчиксравнений}

if not(prosm) and (ver[p]=key)then {if ver[p]=key...}

begin

find:=true;

exit; {поискокончен}

end;

{вывод (просмотр) информации вершины}

if prosm then begin

if wherex>=79 thenwriteln;

write(ver[p],' ');

end;

o9:=oo;

for u:=1 to o9 do {u изменяется в диапазоне размераочереди}

begin

rebro:=false;{связимеждуver[v] иver[u] нет}

{указатель на начало списка связей v-й вершины}

m[v]:=lst[v];

while m[v]<>nil do

begin {поиск значения ver[u] всписке связей v-й вершины}

if m[v]^.inf=ver[u] then begin

{реброесть} rebro:=true;

break;

end;

m[v]:=m[v]^.next; {ребрапоканет...}

end;

{если связь не установлена, поищем связь с ver[v] в спискеu-й вершины, т.е. наоборот...}

if not(rebro) then

begin

m[u]:=lst[u];{указатель на начало спискасвязей u-й вершины}

while m[u]<>nil do

begin

if m[u]^.inf=ver[v]then begin

rebro:=true;

break;

end;

m[u]:=m[u]^.next;

end;

{если связь все таки есть и u-я вершина еще нерассмотрена...}

if rebro and Nw[u] then

begin

inc(oo); {вставка u в начало очереди}

for op:=oo downto 2 do ocher[op]:=ocher[op-1];

ocher[1]:=u;

Nw[u]:=False;{флаг на вершину с индексом u}

end;

{------------------------------------------------------

***Процедура просмотра графа***}

Procedure Write_S(key: longint;prosm: boolean;

var find: boolean;var schet: word);

begin

{инициализация признаков просмотра вершин}

for i:=1 to raz do Nw[i]:=true;

for i:=1 to raz do

{если из raz вершин i-ая неиспользована, то смотреть граф с i-ой вершины}

if Nw[i] and not(find) then WS(i,find,schet);

end;

{------------------------------------------------------

***Процедура сортировки вершин по неубыванию***}

procedure Sort;

begin

for l:=1 to raz-1 do

for j:=1 to raz-l do

if ver[j]>ver[j+1] then

begin

exch:=ver[j];

el:=lst[j];

em:=m[j];

ver[j]:=ver[j+1];

lst[j]:=lst[j+1];

m[j]:=m[j+1];

ver[j+1]:=exch;

lst[j+1]:=el;

m[j+1]:=em;

end;

{=====================================================}

begin

while menu<>'4' do

begin

textmode(1);

textbackground(blue);

clrscr;

textcolor(red);

gotoxy(16,3); writeln('Г Р А Ф Ы');

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

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

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

writeln('Created by AndrewSpikhailo');

gotoxy(15,24); write('ARMAVIR2001');

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 thenrelease(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 (raz<=0) or(raz>400) then begin

raz:=0;

gotoxy(38,wherey-1);

write('ERROR...');

delay(1000);

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' thenmgsi:=true

elsemgsi:=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' thenbegin

Sort;

sor:=true;

end;

prosm:=false;

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

readln(key); writeln;

start(t);

kols:=0;

for fil:=1 to 10000do

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.

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

/> /> /> /> /> /> <td/> /> /> />/>

/>/>/> 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 208315 417 309 723 963 250 561 966 790 982 965 446 228 1 344 446 237 552 912 756142 875 665 83 863 265 369 427 0 476 253 987 537 135 768 374 117 86 12 204 149849 694 332 219 600 738 310 532 358 882 844 394 285 899 302 940 293 276 569607 350 478 806 95 190 153 891 774 322 876 605 798 525 310 851 399 246 876 46491 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 204208 219 228 237 246 250 250 253 265 276 285 293 302 308 309 310 310 315 322 332344 350 358 369 374 386 394 399 417 427 446 446 446 464 476 477 478 525 532537 552 555 561 567 569 575 591 600 605 607 627 665 694 716 723 738 756 768774 777 790 798 806 844 849 851 863 875 876 876 882 891 899 905 912 923 940963 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 76542 822 188 102 85 361 193 137 582 756 241 325 234 400 482 104 416 826 611 874500 505 805 365 134 436 606 755 278 513 684 151 42 895 633 291 621 873 249 566877 965 925 747 359 220 126 991 823 970 79 18 524 513 127 551 851 462 403 37588 739 754 645 357 457 82 274 23 171 523 537 131 227 148 231 657 201 88 12 620660 273 759 359 725 191 88 517 178 361 361 527 92 412 803 656 220 967 597 889625 740 50 219 289 519 202 120 687 957 483 263 554 353 273 769 330 825 486 54626 566 520 501 487 96 201 682 288 677 570 647 745 329 619 594 787 100 348 70661 523 736 286 699 434 505 345 659 558 767 930 339 559 923 246 477 449 428 262152 551 269 552 182 421 277 286 252 408 624 157 746 782 119 302 534 581 163 506184 622 470 239 341 330 908 326 255 318 89 294 696 884 536 687 729 849 570 903100 412 251 359 207 930 994 3 888 816 722 499 517 955 649 619 145 328 80 633657 752 805 761 195 920 978 963 318 152 560 634 643 533 715 982 950 369 742156 980 111 421 401 411 194 876 797 756 449 306 387 158 3 213 719 314 861 968122 21 570 826 242 79 648 768 660 520 702 755 610 420 391 267 114 759 683 23577 71 46 722 136 875 526 966 306 108 858 644 729 54 46 460 71 499 85 428 356103 737 445 289 210 538 31 371 595 466 328 342 874 924 727 757 563 981 730 73423 18 911 181 769 228 73 43 886 626 977 359 527 483 236 196 741 382 250 731 95291 273 51 843 342 988 453 621 228 190 296 897 399 438 703 663 466 789 656 110504 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 7071 71 73 77 79 79

80 82 85 85 86 88 88 88 89 92 95 96 100 100 102 103 103 104108 110 111 114 119 120 122 126 127 131 134 136 137 143 145 148 151 152 152 154156 157 158 163 171 178 181 182 184 188 190 191 193 194 195 196 201 201 202 207210 213 219 220 220 226 227 228 229 231 234 235 236 239 241 242 244 246 249 250251 252 255 260 262 263 267 269 273 273 273 274 277 278 286 286 288 289 289 289291 291 294 296 302 306 306 314 318 318 325 326 328 328 329 330 330 333 338 339341 342 342 345 348 353 353 356 357 359 359 359 359 361 361 361 364 365 369 371375 382 387 391 399 400 401 403 408 411 412 412 413 416 420 421 421 428 428 434436 436 438 445 449 449 453 457 460 462 466 466 470 477 482 483 483 486 487 499499 500 501 504 505 505 506 513 513 515 517 517 519 520 520 523 523 524 526 527527 531 533 534 536 537 538 540 544 546 548 551 551 552 554 558 559 560 563 566566 570 570 570 570 573 581 582 583 594 595 597 606 610 611 611 619 619 620 621621 622 624 625 626 633 633 634 643 644 645 647 648 649 650 656 656 657 657 659660 660 661 663 663 677 682 683 684 687 687 696 699 701 702 703 709 715 719 722722 725 727 729 729 730 731 734 736 737 739 740 741 742 745 746 747 752 754 755755 756 756 757 759 759 759 761 765 767 768 769 769 782 787 789 796 797 803 805805 816 822 823 825 826 826 843 849 851 858 861 873 874 874 875 876 877 884 886888 889 895 897 903 908 911 915 920 923 924 925 930 930 950 955 957 960 963 963963 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

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