Пошук у глибину Алгоритм пошуку в глибину



Сторінка1/21
Дата конвертації04.12.2018
Розмір1.23 Mb.
Назва файлуТеорія Дискретні моделі в САПР.docx
  1   2   3   4   5   6   7   8   9   ...   21

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

Нехай G=(V, E) - простий зв'язний граф, усі вершини якого позначено попарно різними символами. У процесі пошуку вглиб вершинами графа G надають номери (DFS-номери) та певним способом даних для збереження множин, яку називають стеком. Зі стеку можна вилучити тільки той елемент, котрий було додано до нього останнім: стек працює за принципом "останній прийшов - перший вийшов". Інакше кажучи, додавання й вилучення елементів у стеку відбувається з одного кінця, який називається верхівкою стеку. DFS- номери вершини х позначають DFS(х).

Алгоритм

Наведемо кроки алгоритму



  1. Почати з довільної вершини v. Виконати DFS(v):=1. Включити цю вершину в стек.

  2. Розглянути вершину у верхівці стеку: нехай це вершина х. Якщо всі ребра, інцидентні вершині х, позначено, то перейти до кроку 4, інакше - до кроку 3.

  3. Нехай {x,y} - непозначене ребро. Якщо DFS(у) уже визначено, то позначимо ребро {x,y} потовщено суцільною лінією, визначити DFS(у) як черговий DFS-номер, включити цю вершину в стек і перейти до кроку 2.

  4. Виключити вершину х зі стеку. Якщо стек порожній, то зупинитись, інакше - перейти до кроку 2.





Поділіться з Вашими друзьями:
  1   2   3   4   5   6   7   8   9   ...   21


База даних захищена авторським правом ©bezref.in.ua 2019
звернутися до адміністрації

    Головна сторінка