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