Поиск в глубину

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

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

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.

Идея поиска в глубину формулируется следующим образом: начиная с некоторой вершины (например, первой) идем «вглубь» пока это возможно. Далее выбирается вершина u, смежная с v. Процесс повторяется с вершиной u. Если на очередном шаге оказалось что нет непросмотренных вершин связанных с текущей, то выполняется возврат к предыдущей вершине и ищется новая вершина, связанная с ней. Если такой вершины не найдено, то выполняется еще один шаг возврата к предыдущей вершине, и так до тех пор, пока вычислительный процесс не вернется к вершине, с которой начат просмотр.

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

(1) (7)

(3)

(2)

(6)

(5)

(4)

(8)

(9)

Рисунок 8. Очередность просмотра вершин при поиске в глубину.

При реализации поиска используется второй способ представления графа-перечень списков смежных вершин. Описание элементов списка очевидно. Для хранения значений указателей на первые элементы списков для каждой вершины графа используется массив А. номера вершин записываются в массив Rez в той очередности, в которой они просматриваются в процессе поискав глубину (рис. 8 числа в круглых скобках). Для фиксации признака, просмотрена вершина графа или нет, требуется массив Nnew с элементами логического типа.

Program Graph_Deths;

Const MaxN=10;

Type pt=^elem;

Elem=Record

data:integer;

next:pt

End;

MyArray=Array [1...MaxN] Of pt;

MyNew=Array [1...MaxN] Of Boolean;

MyRez=Array [1...MaxN] Of Integer;

Var A:MyArray;

{*Массив указателей на первые элементы списков.*}

Nnew:MyNew;

{*Массив признаков просмотренных вершин графа.*}

Rez:MyRez;

{*Очередность просмотра вершин графа*}

N, cnt:Integer;

{ *Количество вершин в гарфе. Счетчик числа записей в массив Rez.*}

Procedure Insert_List_End (Var t:pt;x:Integer);

{* Вставка элемента в конец списка. Процедура рассмотрена на предыдущих занятиях.*}

Procedure Init; { *Ввод и инициализация данных. Структура входного файла: в первой строке количество вершин графа (N); затем N строк, по одной на каждую из вершин графа. Первое число в строке-количество ребер выходящих из вершины, а затем номера вершин, с которыми связана текущая вершина. Справа по тексту приведен пример входного файладля графа, рассмотренного ранее.*}

Var i,j,w,q:Integer;

Begin

Cnt:=0;

Assign (Input.’Input.txt’); Reset (Input);

Readln (N); {*количество вершин графа*}

For i:=1 To N Do

Begin

A[i]:=Nil; Nnew [i]:=True; Rez [i]:=0

End;

For i:=1 To N Do

Begin

Read (q);

{* Степень вершины графа-число ребер, связанных с данной вершиной.*}

For j:=1 To q Do

Begin

Read (w);

Insert_List_End (A[i],w)

End;

End;

Close (Input);

End;

Procedure Inc_Rez (v:Integer);

Begin

Inc (cnt); Rez [cnt]:=v;

End;

Procedure Search_Depths (v:Integer);

{* Рекурсивный вариант процедуры поиска в глубину.*}

Var t:pt;

Begin

Nnew [v]=False;

{* Помечаем вершину как просмотренную.*}

While t<>Nil Do

Begin

If Nnew [t^.data] Then

Begin

{* если вершина не просмотрена, то записываем ее номер в результирующий массив и идем ‘вглубь’, т.е. к этой вершине.* }

Inc_Rez (t^.data);

Search_Depths (t^.data);

End;

t:=t^.next;

{* Переход к следующему элементу списка.*}

End;

End;

Procedure Print; {* Вывод результата.* }

Var i:Integer;

Begin

Assign (Output, ‘Output.txt’); ReWritw (Output);

For i:=1 To N Do Write (Rez[i], ‘ ‘);

Writeln;

Close (Output);

End;

Begin {* Один из вариантов основной программы.*}

Init;

Inc_Rez (1);

Search_Depths (1);

Print;

End.

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

DRAM (Dynamic random access memory, Динамическая память с произвольным доступом) — тип энергозависимой полупроводниковой памяти с произвольным доступом; DRAM широко используемая в качестве оперативной памяти современных компьютеров, а также в качестве постоянного хранилища информации в системах, требовательных к задержкам.

Язык программирования Оккам (англ. Occam) — это процедурный язык параллельного программирования высокого уровня, разработанный в начале 80-х годов группой учёных из Оксфорда под руководством Дэвида Мэя (англ. David May) по заданию английской компании INMOS Ltd. в рамках работ по созданию транспьютеров. Назван в честь английского философа XIV века Уильма Оккамского, а его сентенция, известная как бритва Оккама, является девизом проекта.

Дата добавления: 2015-08-31