35. Розкрити алгоритм пошуку у глибину (dfs).

Алгори́тм пошуку́ в глибину́ (англ. Depth-first search, DFS) — алгоритм для обходу дерева, структури подібної до дерева, або графа. Робота алгоритма починається з кореня дерева (або іншої обраної вершини в графі) і здійснюється обхід в максимально можливу глибину до переходу на наступну вершину.

-Усі вершини графа мітимо як "нова".

-Вибираємо вершину v0 початкового графа, яка буде коренем дерева. Замінюємо її мітку на "використана". Надаємо значення: v = v0.

- Якщо є вершини w, що суміжні (сполучені ребром) з вершиною v і мають мітку "нова", виконаємо такі дії:

вибираємо одну з такик вершин w і замінюємо її мітку на "використана";

надаємо значення v = w і знову починаємо виконання пункту 3.

-Якщо вершина v відмінна від v0, замінюємо поточну величину v на її безпосереднього предка і повторюємо виконання кроку 3.

-Зауваження 1. Для перебору всіх можливих дерев за допомогою викладених методів на кроці 3 обох алгоритмів маємо передбачити перебір усіх можливих множин вершин і відповідних ребер, які можливо долучити на цьому кроці.

36. Розкрити алгоритм пошуку у ширину.

По́шук у ширину́ — алгоритм пошуку на графі.

Якщо задано граф G = (V, E) та початкову вершину s, алгоритм пошуку в ширину систематично обходить всі досяжні із s вершини. На першому кроці вершина s позначається, як пройдена, а в список додаються всі вершини, досяжні з s без відвідування проміжних вершин. На кожному наступному кроці всі поточні вершини списку відмічаються, як пройдені, а новий список формується із вершин, котрі є ще не пройденими сусідами поточних вершин списку. Для реалізації списку вершин найчастіше використовується черга. Виконання алгоритму продовжується до досягнення шуканої вершини або до того часу, коли на певному кроці в список не включається жодна вершина. Другий випадок означає, що всі вершини, доступні з початкової, уже відмічені, як пройдені, а шлях до цільової вершини не знайдений.

Алгоритм має назву пошуку в ширину, оскільки «фронт» пошуку (між пройденими та непройденими вершинами) одноманітно розширюється вздовж всієї своєї ширини. Тобто, алгоритм проходить всі вершини на відстані k перед тим як пройти вершини на відстані k+1.

-Вибираємо вершину v0 початкового графа. Надаємо значень: L(v0) = 0; V T = {v0}; l = 0.

-Вибираємо вершину vl з множини V T, при якій L(vl) = l.

-Вибираємо вершину v з різниці множин V \ V T, що суміжна (тобто сполучена ребром) з vl долучаємо:

вершину v до множини V T;

ребро (vl; v) до множини E T

і надаємо значення: L(v) = l + 1.

-Крок 3 здійснюємо доти, поки не буде розглянуто всі вершини з V \ V T, що постійно змінюється.

-Кроки 2–4 здійснюємо доти, поки не переберемо всі вершни vl з множини V T, при яких L(vl) = l.

Збільшуємо величину l на 1.

-Кроки 2–6 здійснюємо до споравдження рівності V = V T.

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