Обхід графів в ширину і глибину

Обхід графа в глибину

На кожному кроці пошуку в глибину алгоритм вибирає нову вершину, суміжну з поточної і продовжує пошук вже з неї. Таке «поглиблення» триває до тих пір, поки не буде знайдена вершина, суміжна з кінцевої або алгоритм не заходить у глухий кут. Функція повертає пару (результат, шлях), де результат являє собою прапорець, який показує наявність шляху.


1. початок; функція breadth (G, Start, Finish)

      *обхід графа в ширину
      *G - граф,
      *Finish - початкова вершина,
      *Start - кінцева вершина

2. помітити вершину Start як оброблену;
3. вибрати дугу (Start, X), таку, що вершина X не оброблена, якщо дуги немає - перехід на п.4;
3.1. якщо в G є дуга (Start, Finish) - повернути (true, (Start, Finish));
3.2. (Res, Path): = breadth (G, X, Finish);
3.3. якщо Res = true - повернути (true, (Start, X) + Path);
3.4. повернути breadth (G, Start, Finish);
4. кінець - повернути (false, ()).

В результаті рекурсивного виклику (п. 3.2) може бути знайдений шлях, що проходить через одну із суміжних з Start дуг. Якщо шлях знайдений - то його необхідно доповнити відповідною дугою (п.3.3), в іншому випадку - перейти до пошуку шляху, що проходить через іншу дугу (п. 3.4).

Обхід графа в ширину

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

1. початок; функція breadth (G, Queue_add, Queue_proc, Finish, Res)
        *обхід графа в ширину
        *G - граф,
        *Queue_add - черга доданих вершин (не оброблені)
        *Queue_proc - черга оброблених вершин
        *Finish - кінцева вершина
        *Res - список використаних дуг
2. якщо Queue порожній - повернути (false, Res);
3. отримати H вузол з початку Queue_add;
4. якщо H = Finish - повернути (true, Res);
5. adj_nodes: = список вершин, суміжних з H;
6. видалити з adj_nodes вершини, присутні в Queue_add або Queue_proc;
7. видалити H з Queue_add, додати H в Queue_proc;
8. додати в кінець Queue_add вершини з adj_nodes;
9. додати в Res дуги між вузлом H і вершинами з adj_nodes;
10. повернути breadth (G, Queue_add, Queue_proc, Finish, Res);
11. кінець.

За алгоритмом пошук триває поки не будуть оброблені всі доступні вершини (п. 2), або не приймете сигнал бажаної вершина (п.4). Функція breadth вибирає вершину з початку черги обробки (п.3), і додає нові в кінець (п.8) - за рахунок цього забезпечується необхідний порядок обходу - чим більше вузол віддалений від стартовою вершини - тим пізніше він буде оброблений. Для усунення зациклення алгоритму, в чергу додаються тільки вершини, що не були оброблені або додані в чергу обробки на попередніх кроках (п.6).

І ще тут