Поиск в глубину

пример

Для следующего графика:

поиск в глубину, начинающийся с A, при условии, что левые ребра в показанном графике выбраны перед правыми, и при условии, что поиск запоминает ранее посещенные узлы и не повторяет их (так как это небольшой график), будет посещать узлы в следующем порядке: A, B, D, F, E, C, G. Ребра, пройденные в этом поиске, образуют дерево Тремо, структуру с важными приложениями в теории графов. Выполнение одного и того же поиска без запоминания ранее посещенных узлов приводит к тому, что навсегда посещенные узлы в порядке A, B, D, F, E, A, B, D, F, E и т. Д. Попадают в A, B, D, F , E цикл и никогда не достигнет C или G.

Итеративное углубление - это один из методов, позволяющих избежать этого бесконечного цикла и охватить все узлы.

Вывод поиска в глубину

Четыре типа ребер, определяемых остовным деревом

Удобное описание поиска графа по глубине в терминах остовного дерева вершин, достигнутых во время поиска. На основе этого остовного дерева ребра исходного графа можно разделить на три класса: прямые ребра, которые указывают от узла дерева на одного из его потомков, задние ребра, которые указывают от узла к одному из его предков, и поперечные края, которые не делают ни. Иногда ребра дерева, ребра, которые принадлежат самому остовному дереву, классифицируются отдельно от передних ребер. Если исходный граф не является ненаправленным, то все его ребра являются ребрами дерева или задними ребрами.

DFS заказ

Порядок вершин

Также можно использовать поиск в глубину, чтобы линейно упорядочить вершины графа