Структура данных - первый проход по глубине
Алгоритм поиска в глубину (DFS) перебирает график в движении вглубь и использует стек для запоминания, чтобы получить следующую вершину для начала поиска, когда тупик возникает на любой итерации.
Как и в приведенном выше примере, алгоритм DFS переходит сначала от S к A, от D к G, от E к B, затем к F и, наконец, к C. В нем применяются следующие правила.
Правило 1 - Посетите соседнюю не посещенную вершину. Отметить как посещенный Покажите это. Толкните его в стопку.
Правило 2 - Если соседняя вершина не найдена, вытащите вершину из стека. (Появятся все вершины из стека, у которых нет смежных вершин.)
Правило 3 - Повторяйте Правило 1 и Правило 2, пока стек не опустеет.
| шаг | пересечение | Описание |
|---|---|---|
| 1 |  | Инициализировать стек. |
| 2 |  | Отметьте S как посещенный и поместите его в стек. Исследуйте любой не посещенный соседний узел из S. У нас есть три узла, и мы можем выбрать любой из них. Для этого примера мы возьмем узел в алфавитном порядке. |
| 3 |  | Отметьте A как посещенный и поместите его в стек. Исследуйте любой не посещенный соседний узел из A. И S, и D смежны с A, но нас интересуют только не посещенные узлы. |
| 4 |  | Посетите D и отметьте его как посещенный и положите в стек. Здесь у нас есть узлы B и C , которые соседствуют с D и оба не посещаются. Однако мы снова будем выбирать в алфавитном порядке. |
| 5 |  | Мы выбираем B , отмечаем его как посещенный и помещаем в стек. Здесь B не имеет ни одного не посещенного соседнего узла. Итак, мы выталкиваем B из стека. |
| 6 |  | Мы проверяем вершину стека для возврата к предыдущему узлу и проверяем, есть ли у него какие-либо не посещенные узлы. Здесь мы находим D на вершине стека. |
| 7 |  | Единственный не посещенный соседний узел от D теперь C. Поэтому мы посещаем C , помечаем его как посещенный и помещаем в стек. |
Поскольку C не имеет ни одного не посещенного соседнего узла, мы продолжаем выталкивать стек, пока не найдем узел, у которого есть не посещенный соседний узел. В этом случае их нет, и мы продолжаем появляться, пока стек не опустеет.
Чтобы узнать о реализации этого алгоритма на языке программирования C, нажмите здесь .