Алгоритм пошуку (або обходу) в глибину

Алгоритм пошуку (або обходу) в глибину

 (англ. Depth-first search, DFS)

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

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

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

1.  Піти в якусь суміжну вершину.
2. Обійти все, що досяжне з цієї вершини.
3. Повернутися в початкову вершину.
4. Повторити алгоритм для всіх інших невідвіданих вершин, суміжних з початковою.

Для реалізації алгоритму знадобиться відзначати, в яких вершинах був дослідник, а в яких - ні. Позначку робитимемо в списку Visited, де Visited [i] = True для відвіданих вершин, і Visited [i] = False для невідвіданих. Позначка «про відвідування вершини» ставиться при заході в цю вершину.

 Алгоритм обходу в глибину оформимо у вигляді рекурсивної процедури DFS, де start - номер вершини, з якої запускається обхід.

процедура DFS (початок: ціле число);
були: ціле;
почати

  V isited [start]: = true;

для i: = 1 до n зробити

якщо (a [start, i] = 1) і (відвідав [i] = false)

потім DFS (i)

 кінець; 

У цьому алгоритмі n - число вершин у графі, вершини нумеруються числами від 1 до n, таблиця a зберігає матрицю суміжності. Для запуску алгоритму, наприклад, для вершини з номером start необхідно викликати DFS. Після цього виклику всі вершини, доступні з start, будуть відзначені в списку Visited. 

Візуалізація алгоритму пошуку в глибину

 

http://foxford.ru/wiki/informatika/algoritm-poiska-v-glubinu