Описание тега depth-first-search
Поиск в глубину (DFS) - это алгоритм обхода или поиска по дереву, древовидной структуре или графу. Каждый начинает с корня (выбирая какой-либо узел в качестве корня в случае графа) и исследует, насколько это возможно, вдоль каждой ветви перед отслеживанием с возвратом.
1
ответ
Почему DFS не проверяет дочерние элементы узла, который был выбран для разработки, на предмет состояния цели
Извините, если моя грамматика далека от совершенства, английский не мой родной язык. Если я правильно понимаю, DFS выполняет целевой тест для узла, только если он был выбран для разработки, а не во время его создания. Мне это кажется странным, потом…
12 май '15 в 20:48
2
ответа
Python "RuntimeError: превышена максимальная глубина рекурсии" при поиске в глубину
Я пытаюсь реализовать алгоритм поиска в глубину (DFS) для ориентированных графов, как описано в Cormen et al., Введение в алгоритмы (3-е изд.). Вот моя реализация до сих пор: import pytest from collections import OrderedDict import copy class Node(o…
21 авг '17 в 12:46
2
ответа
2 проблемы о рекурсивной DFS
/* Problem 22 Generate Parentheses: Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.For example, given n = 3, a solution set is: "((()))", "(()())", "(())()", "()(())", "()()()" */ public List&l…
12 фев '16 в 21:41
15
ответов
Когда целесообразно использовать поиск в глубину (DFS) по сравнению с поиском в ширину (BFS)?
Я понимаю разницу между DFS и BFS, но мне интересно знать, когда практичнее использовать один поверх другого? Может ли кто-нибудь привести примеры того, как DFS превзойдет BFS и наоборот?
26 июл '10 в 07:24
1
ответ
Итеративная глубина, первый поиск для поиска строки (2D Array)
Я пытаюсь создать итеративный подход к изумительной игре. Класс содержит поля для двумерного массива строк, называемого "board", и имеет двумерный массив логических значений, называемый "haveVisit". Метод, который вызывает test 2, проходит по всей д…
18 июл '15 в 03:47
2
ответа
Найти все пути в диаграмме FlowChart?
Я сделал редактор диаграмм FlowChart на Java. Он создает потоковые диаграммы и соединяет их друг с другом и создает два массива. Один из них показывает соединительные узлы и линии, другой показывает соединительные элементы друг за другом. Я должен н…
16 мар '10 в 22:09
2
ответа
Полезные классы / методы C# для программ DFS и BFS
У меня есть XML-файл узлов с их соединениями. Что-то вроде: <Graph> <Node Name = "A"> <ConnectsTo>B</ConnectsTo> <ConnectsTo>H</ConnectsTo> </Node> <Node Name="B"></Node> <Node Name="C"> &l…
23 апр '15 в 14:29
1
ответ
BFS и DFS в списке смежности
Таким образом, я знаю основы поиска в ширину и поиска в глубину на графиках, но я не могу понять, как выполнить их оба в списке смежности. Каждый поиск начинается с 0. 0 -> 5 -> 2 -> 1 -> 6 1 -> 7 -> 0 2 -> 7 -> 0 3 -> 5 -> 4 4 -> 6 -> 5 -> 7 -> 3 5…
07 май '13 в 04:05
1
ответ
Как распечатать дерево по порядку, используя поиск по стопке и глубине?
import java.util.LinkedList; import java.util.Queue; class Node { public int iData; // data item (key) public double dData; // data item public Node leftChild; // this node's left child public Node rightChild; // this node's right child public int l…
30 ноя '14 в 10:51
2
ответа
DFS на отключенных графиках
Как DFS(G,v) ведет себя для несвязных графов? Предположим, что граф имеет 3 связанных компонента, и DFS применяется к одному из этих 3 связанных компонентов, а затем мы посещаем каждый компонент или только тот, к которому применяется вершина DFS. Зн…
25 янв '17 в 05:56
2
ответа
Подсчет количества четверок целых чисел
Я видел этот вопрос сегодня, где нам нужно посчитать количество четверок целых чисел (X1, X2, X3, X4)так, что Li ≤ Xi ≤ Ri для i = 1, 2, 3, 4 и X1 ≠ X2, X2 ≠ X3, X3 ≠ X4, X4 ≠ X1. input: Li Ri 1 4 1 3 1 2 4 4 output: 8 1 2 1 4 1 3 1 4 1 3 2 4 2 1 2 …
20 май '15 в 15:11
1
ответ
Список смежности для создания графика и поиска в ширину (BFS) и поиска в первый раз (DFS)
Вот мой код, который реализует граф с использованием списка смежности и выполняет поиск в ширину (BFS) и поиск в глубину (DFS). При создании графа и добавлении ребер я сталкиваюсь с проблемой ошибки при создании графа. Я не уверен в указателе, котор…
26 окт '13 в 21:31
2
ответа
Итератор вектора вызывает ошибку сегментации 11 при попытке поиска в глубину на графике
Я пытаюсь использовать DFS на основе векторного итератора для вычисления наибольшего связанного кластера сгенерированного графа. Однако, когда график имеет определенный размер (вероятность заполнения выше 0,4), в функции DFS возникает ошибка 11 сегм…
26 окт '17 в 07:58
0
ответов
Цикл обнаружения программы DFS завершается с ошибкой ключа
Я пытаюсь реализовать обнаружение цикла в группе обеспечения доступности баз данных, и я использую словарь для отслеживания вершин, которые находятся в стеке рекурсии, устанавливая для их значений значение True в словаре. Как только они выходят, я у…
20 сен '17 в 08:17
1
ответ
Реализация первого обхода глубины на основе стратегии в Python
Добрый день. У меня проблема с реализацией поиска в глубину на основе стратегии, которая определяется в классе Strategy.py. Существует также граф и класс обхода. Класс обхода хорошо отвечает за обход графа. Класс стратегии выглядит следующим образом…
24 апр '12 в 22:18
0
ответов
Java AI найти решение для NxN Puzzle
Прежде всего, много кода, потому что я действительно не знаю, где моя проблема, я прошу прощения! Я делаю программу, которая решает головоломку с переменным размером, например, (3x3 с 0-8). Ноль представляет пустую плитку, цель которой - перемещать …
14 апр '14 в 07:43
1
ответ
Найти путь к указанному узлу в двоичном дереве (Python)
У меня проблемы с вычислением пути от корня к указанному узлу в двоичном дереве (это конкретно о Python-решении этой проблемы). Вот пример. Учитывая приведенное ниже двоичное дерево, если я укажу узел, значение которого равно 4, я хочу вернуть [1, 2…
12 мар '18 в 02:56
0
ответов
Обход дерева Python K-ary выдает ошибку при значении словаря 2 или более
Я предвосхищу это с помощью этого побочного рабочего проекта, чтобы помочь компании и начать обучать меня Python. Это немного продвинуто для меня. У меня есть отчет Excel, который включает в себя список From Nodes а также To Nodes что мне нужно выпо…
28 янв '18 в 16:30
1
ответ
Идеальный алгоритм для нахождения всех путей в графе
Давайте возьмем этот график для примера: Теперь предположим, что я начинаю с вершины 3 и хочу найти вершину 7. При первом поиске по глубине (в зависимости от реализации) сначала будут рассматриваться дочерние элементы. Теперь в нашем примере ради ар…
23 сен '13 в 07:09
2
ответа
Поиск в глубину - Как конечный граф может генерировать бесконечное дерево
Я только начал свой последний год обучения и столкнулся с проблемой, с которой мне нужна помощь. Я посмотрел на поиск в глубину и понял, что в бесконечном дереве он не может найти решение из-за того, что всегда выбирает крайний левый путь, однако я …
05 авг '14 в 23:55