Публикации по теме 'depth-first-search'
Обход графа — Поиск в ширину и поиск в глубину (часть 2)
В моей последней статье о поиске в ширину и поиске в глубину я объяснил оба типа обхода графа и немного рассказал о плюсах и минусах каждого из них. В этой статье я сосредоточусь на том, как мы можем реализовать каждый тип алгоритма с помощью JavaScript!
Во-первых, давайте быстро повторим то, что было объяснено в прошлой статье.
Поиск в ширину (BFS)
Алгоритм обхода графа, который обходит граф по одному уровню за раз. Он посещает всех детей родителя, затем посещает всех внуков и..
Поиск в глубину
Что это?
Поиск в глубину (DFS) — это алгоритм обхода или поиска древовидных или графовых структур данных. Алгоритм начинается с корневого узла и исследует каждую ветвь, насколько это возможно, перед возвратом.
Как ты это делаешь?
Три метода DFS:
Предзаказ Почтовый заказ Чтобы
Главная идея
Для всех трех методов:
вы посещаете узел вы исследуете всю левую сторону вы исследуете всю правую сторону пройти налево пройти направо
Предзаказ
Создайте переменную для хранения..
Вопросы по теме 'depth-first-search'
Сохранение информации о пути в алгоритме Крускала
Я сгенерировал минимальное остовное дерево с помощью алгоритма Крускала и хотел знать, как хранить пути.
Это мое минимальное остовное дерево
Loc1 | Loc2 | Distance
02 | 10 | 2.00 Km
05 | 07 | 5.39 Km
02 | 09 | 5.83 Km...
367 просмотров
schedule
08.11.2021
Как я могу определить, существует ли путь между всеми вершинами, используя рекурсивный алгоритм поиска в глубину?
Я пытаюсь понять, сильно ли связан график или нет. Чтобы считаться сильно связным, граф должен обладать следующими свойствами: 1) алгоритм DFS объявляет, что все узлы достижимы из начальной вершины 2) Когда все направления ребер меняются местами...
301 просмотров
schedule
30.09.2021
Является ли классический (основанный на рекурсии) поиск в глубину более эффективным с точки зрения памяти, чем DFS на основе стека?
Я смотрел ответы на этот вопрос @AndreyT, и у меня возник вопрос относительно эффективности памяти классической DFS по сравнению с DFS на основе стека. Аргумент состоит в том, что классическая DFS с обратным отслеживанием не может быть создана из...
1479 просмотров
schedule
17.10.2021
Рекурсивный метод шифрования дерева с использованием dfs
Эта проблема не связана с заданием, хотя это несколько типичная проблема, «похожая на задание», которую я пытаюсь решить другим способом.
Я хочу написать метод, который будет рекурсивно проходить через двоичное дерево с использованием алгоритма...
300 просмотров
schedule
28.10.2021
преобразование из поиска в ширину в ограниченный поиск в глубину
Как и все новички в алгоритмах поиска, я работаю над примером старой модной головоломки с 8 задачами, я выполнил алгоритм в первую очередь в ширину, который находится в приведенном ниже коде, и мне было интересно, как преобразовать его в ограниченную...
1316 просмотров
schedule
13.09.2021
Найти все перестановки строки с определенной неизменной позицией
Учитывая Строку слов, скажите «OhMy», оставьте прописную букву фиксированной (неизменной), но мы можем изменить положение строчной буквы. Выведите все возможные перестановки.
например. учитывая "OhMy", он должен выводить ["OhMy", "OyMh"]
Вот...
226 просмотров
schedule
27.09.2021
Отмена поиска в глубину или обход предварительного заказа
Допустим, у меня есть полный двоичный график высотой 2, примерно так:
0
1 2
3 4 5 6
где есть ребро от 0 до 1 и от 0 до 2, от 1 до 3 и от 1 до 4, от 2 до 5 и от 2 до 6.
Я могу получить узлы в глубине первого...
2179 просмотров
schedule
19.11.2021
Точка сочленения неориентированного графа
Меняются ли тип и количество точек сочленения при изменении точки входа (корневого узла) для неориентированного графа?
Если он меняется, то почему это происходит?
Я понимаю, что количество баллов может отличаться, но почему количество баллов...
343 просмотров
schedule
04.10.2021
Поиск в глубину, рекурсия, циклы For и возврат
Я пытаюсь реализовать алгоритм DFS, чтобы выяснить, есть ли путь между узлом start и узлом target . Вот код, который у меня есть:
# Depth-first search
def find_path2(s, t):
s.visited = True
if s.data == t.data:
return True...
772 просмотров
schedule
08.09.2021
OutputError: найти самый длинный путь в матрице с заданными ограничениями
Моя матрица:
4 8 7 3
2 5 9 3
6 3 2 5
4 4 1 6
Проблема (катание на лыжах):
Каждое число представляет собой высоту этого участка горы.
Из каждой области (т. Е. Прямоугольника) в сетке вы можете пойти на север , юг , восток ,...
1605 просмотров
schedule
23.10.2021
Подсчитать количество достижимых узлов в направленном графике от каждого узла быстрее, чем O (V ^ 2)?
Итак, у меня есть ориентированный график, который может содержать циклы. Мне нужно для каждого узла подсчитать количество узлов, доступных из этого узла, и сохранить это в таблице. Наивный подход заключался бы в использовании DFS с каждого узла, что...
258 просмотров
schedule
02.10.2021
Что лучше: dfs или bfs для тестирования двудольных на ориентированных графах?
Если я хочу проверить цветность двух тестов / если направленный граф является двудольным, имеет ли значение, использую ли я поиск в ширину или поиск в глубину? Есть ли еще один эффективный с точки зрения временной сложности?
244 просмотров
schedule
22.10.2021
Сравните глубину первой ветви и границы и алгоритм поиска IDA *
Я хочу сравнить и узнать точные различия между алгоритмами первой ветви и границы глубины и алгоритмами IDA *. Я просматривал Интернет, но не могу найти четких объяснений. Пожалуйста помоги!
92 просмотров
schedule
14.11.2021
Как выполнить возврат при использовании итеративной DFS, реализованной через стек
Я решал эту проблему Leetcode: https://leetcode.com/problems/word-search/ , и я случайно выбрал итеративную реализацию DFS с циклом while и стеком, но я столкнулся с некоторыми неудобствами при обратном отслеживании, которых я обычно не выполнял бы,...
400 просмотров
schedule
18.10.2021
Псевдокод и сложность поиска в глубину (DFS) против поиска в ширину (BFS)
Мне нужно разработать псевдокод для алгоритма, который вычисляет количество связных компонентов в графе G = (V, E) с учетом вершин V и ребер E.
Я знаю, что могу использовать поиск в глубину или в ширину для вычисления количества подключенных...
146 просмотров
schedule
06.11.2021
Как заставить алгоритм поиска в глубину Prolog углубиться в дерево? (Применительно к Сокобану)
Я пытаюсь решить загадку Sokoban на Прологе, используя алгоритм поиска в глубину, но Я не могу выполнить глубокий поиск по дереву решений. Я могу исследовать только первый уровень.
Все исходники находятся на Github (ссылки на редакцию, когда...
1038 просмотров
schedule
10.03.2022
Определение размера стека в алгоритме итеративного поиска в глубину (DFS)
Я написал итеративную реализацию алгоритма поиска в глубину (DFS) на C ++. На выходе он производит правильный порядок посещения. Алгоритм такой:
Инициировать массив посещенных [] с ложными значениями.
Вставляем первую вершину в стек....
606 просмотров
schedule
12.03.2022
Пространственная сложность DFS и BFS в графе
Я пытаюсь понять, какова пространственная сложность DFS и BFS на графике. Я понимаю, что пространственная сложность BFS при использовании матрицы смежности будет O(v^2) , где v - количество вершин.
Используя список смежности, сложность...
3074 просмотров
schedule
13.03.2022
Сильно связанные компоненты: алгоритм Косараджу
В алгоритме Косараджу я столкнулся с двумя возможными реализациями:
1) Поиск компонентов сильной связности в обращенном графе в топологическом порядке вершин исходного графа.
2) Поиск компонентов сильной связности исходного графа в...
668 просмотров
schedule
09.04.2022
Определить связность неориентированного графа
Я наткнулся на эту публикацию некоторое время назад:
Лучший алгоритм для определения того, является ли неориентированный граф дерево
В нем говорится, что для того, чтобы определить, является ли неориентированный граф деревом, вам просто нужно...
3153 просмотров
schedule
16.04.2022
