Структура данных - первый проход по глубине

Алгоритм поиска в глубину (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, нажмите здесь .