DFS (первый обход глубины) в структуре данных: что такое, порядок и приложения

Значение DFS в структуре данных

DFS в структуре данных, также известный как обход в глубину, представляет собой рекурсивный алгоритм, в основном используемый для поиска во всех вершинах графа или древовидной структуры данных. Обход — это посещение каждого узла графа. Алгоритм начинается с корневого узла (который может быть произвольным узлом в качестве корневого узла в графе) и проходит насколько возможно вдоль каждой ветви перед возвратом.

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

Алгоритм

Сформулируйте рекурсивную функцию, которая будет принимать индекс узла и посещенный массив.

1. Держите текущий узел помеченным как посещенный, а затем распечатайте его.
2. Пройдитесь по всем примыкающим и непомеченным нотам и вызовите рекурсивную функцию с индексом соседнего узла.

Изучите наши популярные курсы по программной инженерии

Характеристики

Анализ времени и пространства в DFS в структуре данных различается в зависимости от области его применения. Теоретически DFS в основном используется для пересечения полного графа и занимает время O(|V|+|E|), где |V| изображает количество вершин и |E| изображает количество ребер. Этот график линейный.

В этих приложениях пространство O(|V|) также используется в качестве крайней меры для сохранения стека вершин, хранящихся на пути поиска, и набора уже посещенных вершин. Поэтому установка временных и пространственных границ аналогична поиску в ширину. Здесь два используемых алгоритма меньше зависят от их сложности и больше от различных характеристик порядков вершин, создаваемых двумя алгоритмами.

Когда дело доходит до приложений DFS в структуре данных, связанных с конкретными областями, такими как поиск решений в веб-краулинге или ИИ, граф, который требует обхода, может быть слишком большим, чтобы посещать его целиком. В таких случаях поиск выполняется только на ограниченную глубину; из-за ограниченных ресурсов, таких как дисковое пространство или память. Структуры данных обычно не используются для отслеживания набора всех ранее посещенных вершин. Поиск, выполняемый на ограниченной глубине, по-прежнему делает время линейным, когда речь идет о единице расширенных ребер и вершин.

Однако помните, что это число не равно размеру всего графа, поскольку некоторые вершины могут быть просмотрены несколько раз, а другие — нет.

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

Изучайте онлайн-курсы по разработке программного обеспечения в лучших университетах мира. Участвуйте в программах Executive PG, Advanced Certificate Programs или Master Programs, чтобы ускорить свою карьеру.

Алгоритм поиска в глубину

Каждая вершина графа в стандартной реализации DFS делится на одну из двух категорий:

1. Не посещено
2. Посетил

Алгоритм используется для точного определения каждой вершины и пометки их как посещенных и в то же время для предотвращения циклов.

Вот как работает алгоритм DFS:

1. Поместите любую конкретную вершину графа в стек.
2. Элемент на вершине стека должен быть добавлен в список посещенных.
3. Составьте список смежных узлов этой вершины и добавьте узлы, не входящие в список посещенных, на вершину стека.
4. Продолжайте повторять предыдущие шаги, пока стек не опустеет.

Заказ DFS

Упорядочение вершин. Существует четыре способа линейного упорядочения вершин графа или дерева в DFS:

1. Список вершин, расположенных в порядке их первого посещения алгоритмом DFS, называется предварительным порядком. Это краткий способ описать ход поиска.
2. Список вершин в порядке их последнего посещения алгоритмом называется поступорядочением.
3. Список вершин в порядке, противоположном их первому посещению, является обратным предварительным порядком. Поэтому его не следует путать с почтовым заказом.
4. Список вершин в порядке, обратном их последнему посещению, является обратным поступорядочением. Не следует путать с предварительным заказом.

Кроме того, существует упорядочение по порядку и обратное упорядочение для двоичных деревьев.

Поиск в глубину или DFS для графика

DFS для графа почти такой же, как DFS для дерева. Разница лишь в том, что графы могут иметь циклы, в отличие от деревьев. Узел может быть посещен несколько раз , и, чтобы избежать обработки узла, используется логический массив посещений.

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

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

Приложения обхода в глубину (DFS)

Поиск в глубину используется в качестве строительного блока в следующих алгоритмах:

• Поиск компонентов, которые подключены.
• Нахождение компонент 2-(вершинной или реберной) связности.
• Нахождение мостов графа.
• Нахождение компонентов 3-(вершинной или реберной) связности.
• Топологическая сортировка.
• Нахождение компонентов, которые сильно связаны.
• Выяснение сходства вида с тем или иным видом в филогенетическом дереве.
• Проверка плоскостности.
• Составление слов для определения предельного множества любой группы.
• Решение головоломок, которые имеют только одно решение, например, лабиринты.
• Генерация лабиринта .
• Поиск бисвязности в графах.

Псевдокод DFS и реализация в Python

Функция init() запускается на каждом узле в приведенном ниже псевдокоде, чтобы убедиться, что все вершины посещены. Это особенно важно, поскольку графы могут иметь различные несвязанные области.

Вот псевдокод:

DFS(G, и)

u.visited = правда

для каждого v ∈ G.Adj[u]

если v.visited == ложь

ДФС(Г,в)

в этом() {

Для каждого u ∈ G

u.visited = ложь

Для каждого u ∈ G

DFS(G, и)

}

Вот реализация DFS на Python:

график = {

'5' : ['3','7'],

'2' : ['1', '3'],

'6' : ['7'],

'3': [],

'4' : ['6'],

'7': []

}

посетили = установить ()

def dfs (посещено, граф, узел):

если узел не посещается:

печать (узел)

посещенный.добавить(узел)

для соседа в графе [узел]:

dfs(посещено, график, сосед)

print("Это DFS:")

dfs(посещено, график, '5')

Выход:

Это ДФС: 5

Изучите наши популярные курсы по программной инженерии

Сложность поиска в глубину

Джон Рейф исследовал вычислительную сложность поиска в глубину. Точнее, в графе данный факт есть G, пусть O — стандартный порядок, определяемый повторяющимся алгоритмом поиска в глубину. G представляет собой граф, а O представляет упорядоченный вывод избыточного алгоритма DFS. Этот вывод известен как лексикографический порядок DFS.

Вывод

Основная цель алгоритма DFS — посещение каждой отдельной вершины, которая позволяет избежать циклов в целевых графах. Если вы хотите принять участие в расширенных реализациях операций поиска или операций упорядочивания, вам обязательно следует рассмотреть возможность прохождения комплексного курса премиум-класса по поиску в глубину и структуре данных.

В upGrad есть несколько курсов DFS высшего уровня, таких как Master of Science in Computer Science и Specialization in Big Data .

Если вы изо всех сил пытаетесь сделать следующий шаг и ищете экспертный совет, upGrad Mentorship стремится предоставить вам индивидуальные занятия с лучшими консультантами по вопросам карьеры и экспертами в отрасли.