Пошук у глибину (DFS)
Обходить граф, ідучи одним шляхом якомога глибше, а потім повертаючись до останнього розгалуження. Стек на екрані - це і є цей шлях.
- час O(V + E)
- пам'ять O(V)
- використовує стек
Що це означає?
- Вершина: точка графа, тут намальована як кружечок із літерою.
- Ребро: лінія, що з'єднує дві вершини. Тут ним можна пройти в обидва боки.
- Сусіди: вершини, з'єднані з даною вершиною ребром. Їх переглядають в алфавітному порядку.
- Черга: хто перший прийшов, той перший вийшов. BFS завжди бере вершину, яка чекає найдовше.
- Стек: хто останнім прийшов, той першим вийшов. DFS завжди продовжує з вершини, до якої дійшов останньою.
- V і E: кількість вершин і ребер. O(V + E) означає, що кожну вершину й кожне ребро обробляють сталу кількість разів.
- у стеку
- поточна
- готова
- ребро дерева пошуку
- пропущене ребро
Починаємо з вершини A. Натисніть «Відтворити» або проходьте пошук крок за кроком.
Пробіл: відтворення або пауза. Стрілки ліворуч і праворуч: крок. Home і End: на початок або в кінець.
Спробуйте: Оберіть граф із циклами. Кожне пунктирне ребро веде назад до вершини, яка вже в стеку або готова: таке ребро замикає цикл.
Як це працює
DFS викликає сам себе для першого сусіда, якого ще не бачив, потім для першого нового сусіда цієї вершини і так далі. Коли у вершини не лишається нових сусідів, її виклик завершується, а DFS повертається на крок назад і пробує там наступного сусіда. Відкриті виклики утворюють стек, який завжди є шляхом від старту до поточної вершини. Число біля вершини показує, якою за порядком її відвідано.
Коли варто використовувати
DFS допомагає з'ясувати, куди взагалі можна дійти, знайти цикли, пройти лабіринт або впорядкувати завдання, що залежать одне від одного. Найкоротшого шляху він не знаходить.