Пошук у глибину Виконала учениця 11-А класу Серьогіна Ольга

Визначення: Пошук в глибину - це рекурсивний алгоритм обходу вершин графа. Якщо метод пошуку в ширину проводився симетрично (вершини графа проглядалися за рівнями), то даний метод передбачає просування вглиб до тих пір, поки це можливо.

Опис Нехай G=(V, E) - простий зв'язний граф, усі вершини якого позначено попарно різними символами. У процесі пошуку вглиб вершинами графа G надають номери (DFS-номери) та певним способом даних для збереження множин, яку називають стеком.стеком Кожному з елементів логічного масиву visited заздалегідь присвоюється значення false, т. е. кожна з вершин спочатку буде значитися як не відвідування. Двовимірний масив graph - це матриця суміжності графа.

Алгоритм Почати з довільної вершини v. Виконати DFS(v):=1. Включити цю вершину в стек. Розглянути вершину у верхівці стеку 6 нехай це вершина х. Якщо всі ребра, інцидентні вершині х, позначено, то перейти до кроку 4, інакше - до кроку 3. Нехай {x,y} - непозначене ребро. Якщо DFS(у) уже визначено, то позначимо ребро {x,y} потовщено суцільною лінією, визначити DFS(у) як черговий DFS-номер, включити цю вершину в стек і перейти до кроку 2. Виключити вершину х зі стеку. Якщо стек порожній, то зупинитись, інакше - перейти до кроку 2.

Застосування алгоритму 1.Пошук будь-якого шляху в графі. 2.Пошук лексикографічно першого шляху в графі. 3.Перевірка, чи є одна вершина дерева предком інший: На початку і В кінці ітерації пошуку в глибину буде запам'ятовувати "час" заходу і виходу в кожній вершині. Тепер за O(1) можна знайти відповідь: вершина i є предком вершини j тоді і тільки тоді, коли starti endj. 4.Топологічна сортування: Запускаємо серію пошуків у глибину, щоб обійти всі вершини графа. Відсортуємо вершини з часу виходу за спаданням - це і буде відповіддю. 5.Перевірка графа на ацикличность і знаходження циклу 6.Пошук мостів: Спочатку перетворюємо граф орієнтований. Мостами є ті ребра, к кінці яких належать різним сильносвязным компонентів.

Его представление в виде списков смежности имеет следующий вид:

Алгоритм ПОГ вызовет процедуру ПОИСК(1). Эта процедура рекурсивно вызовет ПОИСК(6) и т.д. Вот структура всех получающихся вызовов процедуры ПОИСК: Вначале идут "горизонтальные" вызовы, затем возвраты справа налево и вызовы "по вертикали". В результате вершины G 2 получат следующие номера, отражающие порядок их прохождения:

Задача: uses crt; const n=5; var i, j, start: integer; visited: array[1..n] of boolean; const graph: array[1..n,1..n] of byte = ((0, 1, 1, 0, 1), (1, 0, 1, 1, 0), (1, 1, 0, 0, 0), (0, 1, 0, 0, 1), (1, 0, 0, 1, 0)); {пошук в глибину} procedure DFS(st: integer); var r: integer; begin write(st:2); visited[st]:=true; for r:=1 to n do if (graph[st, r]<>0) and (not visited[r]) then DFS(r); end;

{основний блок програми} begin clrscr ; writeln('Матрица смежности:'); for i:=1 to n do begin visited[i]:=false; {починаємо з того, що вершина не відвідана} for j:=1 to n do write(graph[i, j],' '); writeln; end; write('Стартовая вершина >> '); read(start); writeln('Результат обхода'); DFS(start); { звернення до процедури} end.