Поиск в глубину (DFS) часто используется для обхода и поиска структуры данных в виде дерева или графа. Идея состоит в том, чтобы начать с корня (в случае дерева) или некоторого произвольного узла (в случае графа) и исследовать каждую ветвь как можно глубже, прежде чем выполнять обратный поиск.
Рассмотрим следующий график, который отмечает порядок, в котором узлы будут обнаружены в DFS.
Мы перечислили наиболее часто задаваемые вопросы интервью о структурах данных и алгоритмах, которые могут быть решены с помощью алгоритма DFS -
- Реализация поиска в глубину (DFS)
- Сгенерировать список возможных слов из символьной матрицы
- Найти длину самого длинного пути в матрице с последовательными символами
- Заменить все вхождения 0, окруженные 1, в двоичной матрице
- Заменить все вхождения 0, которые не окружены 1 в двоичной матрице
- Найти все вхождения данной строки в символьной матрице
- Алгоритм заполнения наводнения
- Перейти к заданному каталогу с использованием BFS и DFS в Java
- Типы ребер, участвующих в DFS, и отношения между ними
- Найдите самый длинный путь в направленном ациклическом графе (DAG)
- Найти путь между заданными вершинами ориентированного графа
- Определить, является ли граф двудольным графом с помощью DFS
- Проверить, сильно ли связан граф или нет, с помощью одного обхода DFS
- Найти стоимость кратчайшего пути в DAG за один проход Bellman-Ford
- Проверить, является ли данный граф сильно связным или нет
- Проверить, является ли данный орграф DAG (направленным ациклическим графом) или нет
- 2-сторонняя связность в графике
- Определить, является ли неориентированный граф деревом (ациклический связанный граф)
- Проверить, содержит ли неориентированный граф цикл
- Транзитивное замыкание графа
- Алгоритм топологической сортировки для DAG с использованием DFS
- Найти первые k максимально встречающихся слов в заданном наборе строк
- Найти максимальное слово в заданном наборе строк
- Лексикографическая сортировка заданного набора ключей
- Обход дерева Inorder, Preorder и Postorder
Спасибо.
