Теорія графів.
Лабораторна робота №3.
Тема. Обхід графу в глибину.
Мета. Використовуючи довільну мову програмування, реалізувати алгоритм обходу графу в глибину згідно завдання.
Короткі теоретичні відомості.
Робота алгоритму обходу графу полягає в тому, що алгоритм не зупиняється, поки не будуть відвідані всі доступні вершини. Інакше кажучи, обхід графу. Котрий починається з вершини v, пройде через всі вершини w, до котрих існує шлях. Тому всі вершини можна обійти тільки у зв’язному графі. Таким чином, обхід графу можна використати для встановлення його зв’язності.
Якщо граф не є зв’язним, його обхід, починаючи з вершини v, торкнеться лише підмножини вершин графу. Ця підмножина називається зв’язним компонентом, котрий містить вершину v.
Стратегія пошуку в глибину (DFS – depth-first search) полягає в наступному: обхід, котрий починається з вершини v, продовжується як можна далі в глибину графу, а потім повертається у початкову точку. Інакше кажучи, після відвідування будь-якої вершини стратегія DFS намагається знайти ще не відвідану суміжну вершину (мал. 1).
Загальний алгоритм обходу графу в глибину: