Короткі теоретичні відомості

Теорія графів.

Лабораторна робота №3.

Тема. Обхід графу в глибину.

Мета. Використовуючи довільну мову програмування, реалізувати алгоритм обходу графу в глибину згідно завдання.

Короткі теоретичні відомості.

Робота алгоритму обходу графу полягає в тому, що алгоритм не зупиняється, поки не будуть відвідані всі доступні вершини. Інакше кажучи, обхід графу. Котрий починається з вершини v, пройде через всі вершини w, до котрих існує шлях. Тому всі вершини можна обійти тільки у зв’язному графі. Таким чином, обхід графу можна використати для встановлення його зв’язності.

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

Стратегія пошуку в глибину (DFS – depth-first search) полягає в наступному: обхід, котрий починається з вершини v, продовжується як можна далі в глибину графу, а потім повертається у початкову точку. Інакше кажучи, після відвідування будь-якої вершини стратегія DFS намагається знайти ще не відвідану суміжну вершину (мал. 1).