ПРАКТИЧЕСКОЕ ИСПОЛЬЗОВАНИЕ АЛГОРИТМА ПОИСКА В ГЛУБИНУ

ПРАКТИЧЕСКОЕ ИСПОЛЬЗОВАНИЕ АЛГОРИТМА ПОИСКА В ГЛУБИНУ

Абгалдаева Алина Александровна

магистрант, ФГБОУ ВО "МГТУ "СТАНКИН",

РФ, г. Москва

Пушкин Алексей Юрьевич

научный руководитель, доц., канд. техн. наук, кафедры информационных технологий и вычислительных систем, ФГБОУ ВО "МГТУ "СТАНКИН",

РФ, г. Москва

PRACTICAL USING OF THE DEPTH FIRST SEARCH ALGORITHM

Alina Abgaldaeva

master student, Moscow State University of Technology "STANKIN", Russia, Moscow

Alexey Pushkin

Associate professor of the department information technologies and computer systems, Moscow State University of Technology "STANKIN",

 Russia, Moscow

АННОТАЦИЯ

В данной статье дается обзор практического применения алгоритма поиска в глубину.

ABSTRACT

This article is given an overview of practical using of the depth first search algorithm.

Ключевые слова: алгоритм, поиск в глубину, обнаружение, отслеживание, граф, вершина, ребро, путь.

Keywords: algorithm, depth first search, detecting, tracking, graph, vertex, node, edge, path.

Введение

Алгоритм поиска в глубину пересекает или изучает такие структуры данных как графы или деревья [1].

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

Когда на какой-либо итерации возникает тупиковый путь, алгоритм поиска в глубину пересекает сеть в направлении тупикового пути и использует стек структуры данных, чтобы запомнить получение следующей вершины графа для начала поиска [1].

Пример работы алгоритма для графовой структуры данных изображен на Рисунке 1.

Рисунок 1. Пример работы алгоритма поиска в глубину

Практическое применение

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

1. Топологическая сортировка - используется, в основном, для планирования задач на основе заданных зависимостей между задачами. В информационных науках, приложения данного типа возникают при планировании команд, упорядочении вычислений ячеек формул при повторном вычислении значений формул в электронных таблицах, логическом синтезе, определении порядка выполнения задач компиляции в make-файлах, сериализации данных и разрешении символьных зависимостей в компоновщиках [3];
2. Обнаружение циклов графов - граф имеет цикл, если его обратное ребро можно найти с помощью алгоритма поиска в глубину. Поэтому можно использовать данный алгоритм для обнаружения обратных ребер [1];
3. Поиск сильных связей между компонентами в графе - ориентированный граф можно назвать сильно связным, если его каждая его вершина имеет путь к любой другой вершиной. С помощью алгоритма поиска в глубину можно найти эти связи [1];
4. Поиск пути - алгоритм можно настроить на изучение и поиск пути между двумя определенными вершинами графа. К примеру, мы знаем, что у некоторого графа вершины А, В и С, тогда, чтобы найти путь между А и В нужно использовать вершину С, как стартовую для алгоритма поиска. Отследим путь между стартовой вершиной и следующей вершиной с помощью стека С. Затем путь можно вернуть с помощью алгоритма, как только будет обнаружена вершина С [3];
5. Тестирование графа на двудольность - с помощью алгоритма поиска в глубину или в ширину можно раскрасить новые вершины одной части графа цветами, отличными от цветов вершин противоположной части, при первом их обнаружении. Это позволит убедиться, что ребра, соединяющие одну и ту же часть графа, отсутствуют [1];
6. Решение лабиринтов и других головоломок - алгоритм может обнаружить все возможные решения лабиринта, с помощью узлом текущего пути из посещенного набора[1];
7. Веб-сканеры - поиск в глубину можно использовать в реализации веб-сканеров для исследования ссылок на веб сайты [3];
8. Генерация лабиринтов - алгоритм можно использовать для генерации случайных лабиринтов [3;]
9. Проверка модели на наличии необходимых свойств- с помощью поиска в глубину можно реализовать процессы проверки пересечения свойств модели системы с целевым набором [3];
10.  Обратное отслеживание - поиск в глубину может определить алгоритмы обратного отслеживания [3];

Вывод

Алгоритм поиска в глубину проходит каждый путь максимальной глубины.

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

Список литературы:

1. simplilearn / [Электронный ресурс]. - Режим доступа: URL: https://www.simplilearn.com/tutorials/data-structure-tutorial/dfs-algorithm
2. geeksforgeeks / [Электронный ресурс]. - Режим доступа: URL: https://www.geeksforgeeks.org/applications-of-depth-first-search/