Публикации по теме 'depth-first-search'
Генераторы и поиск в глубину (DFS)
Генераторы ES6
Итак, мне нравится учиться чему-то, сочетая то, что я хочу изучить, с примерами использования в реальном мире. Слишком часто концепции/идеи сочетаются с подходами к обучению, которые никогда не приживаются, потому что они сочетаются с примерами, которые никогда не используются. Таким образом, концепции не затвердевают и даже не обосновываются.
Итак, давайте рассмотрим генераторы и поиск в глубину (DFS). Так вот, за все годы программирования мне ни разу не приходилось..
Алгоритм поиска в глубину
Это моя первая статья на Medium, поэтому, если я допустил какую-либо ошибку или неверное утверждение, сообщите мне об этом в поле для комментариев.
Целевой аудиторией является новичок в информатике. Я собираюсь объяснить немного больше о поиске в глубину.
Предварительные требования: основы представления графа и концепция стека.
Акроним поиска в глубину — DFS. В CS DFS — очень популярный алгоритм теории графов, который на самом деле решает множество реальных задач.
Основная идея..
Демистификация поиска в глубину
Как только вы узнаете достаточно о различных структурах данных, вы начинаете думать про себя: правильно, так… в чем смысл, опять же? Почему у нас вообще есть все эти структуры?
Когда вы садитесь за деревья, очень легко потерять ощущение леса. Но нам пора немного уменьшить масштаб, потому что мы находимся в той точке, где мы наконец-то - наконец-то! - начнем заниматься супер-забавными вещами. Под супер-весельем я подразумеваю алгоритмы !
Я начал эту серию, желая узнать больше обо..
Вопросы по теме 'depth-first-search'
Сначала в ширину против сначала в глубину
При перемещении по дереву / графику какая разница между сначала в ширину и сначала в глубину? Любые примеры кодирования или псевдокода были бы хороши.
122456 просмотров
schedule
06.07.2022
Найти первый нуль в двоичном дереве с ограниченной памятью
У меня есть двоичное дерево, в котором каждый узел может иметь значение.
Я хочу найти узел в дереве, который имеет значение null и находится ближе всего к корню. Если есть два узла на одинаковом расстоянии от корня, подойдет любой. Мне нужно...
669 просмотров
schedule
09.06.2022
найти ближайшего соседа в рекурсивной манере поиска в глубину
Я пытаюсь найти ближайшего соседа в рекурсивной манере поиска в глубину. Прежде чем перейти к этому моменту, необходимо включить много элементов, поэтому для простоты я включил только тот раздел, с которым у меня в настоящее время возникают проблемы....
1711 просмотров
schedule
31.03.2022
Алгоритм подсчета связных компонентов графа в Python
Я пытаюсь написать скрипт, который подсчитывает связанные компоненты графа, и не могу найти правильное решение. У меня есть простой граф с 6 узлами (вершинами), узлы 1 и 2 соединены, а узлы 3 и 4 соединены (6 вершин; 1-2,3-4,5,6). Итак, граф...
9631 просмотров
schedule
23.03.2022
Решение лабиринта с использованием графа
Эй, я был на местном соревновании по программированию, и они задали мне этот вопрос, который я не мог ответить, поэтому, пожалуйста, помогите мне с этим.
Напишите программу, которая загружает из файла размер лабиринта, а затем сам лабиринт. Для...
3477 просмотров
schedule
24.11.2023
Выведите узлы в цикле, существующем в ориентированном графе
Хотя я понимаю, что мы можем обнаруживать циклы с помощью алгоритма DFS, обнаруживая обратные края http://cs.wellesley.edu/~cs231/fall01/dfs.pdf . Я не могу понять, как эффективно и «чисто» выводить узлы в цикле, следуя указанному выше методу....
259 просмотров
schedule
12.10.2023
Классификация ребер в DFS
Согласно книге (Intro to Algorithm), в dfs ребра подразделяются на 4 вида:
Ребро дерева, если в ребре (u,v) впервые обнаруживается v, то (u, v) является ребром дерева.
Задний край, если ......, v уже обнаружен и v является предком, то это...
18498 просмотров
schedule
21.12.2022
Поиск циклов с поиском в глубину на основе стека
Я знаю, что вы используете рекурсивную реализацию DFS, где все узлы начинаются как белые, окрашиваются в серый цвет при первом обнаружении и окрашиваются в черный цвет после изучения всех их дочерних элементов, вы знаете, что существует цикл, если вы...
1612 просмотров
schedule
09.05.2022
Топологическая сортировка пытается отсортировать вершины или ребра?
Всем счастливой пасхи.
В настоящее время я изучаю топологическую сортировку и задаюсь вопросом о том, какая топологическая сортировка пытается сортировать на самом деле.
В Руководстве по разработке алгоритмов топологическая сортировка...
1850 просмотров
schedule
30.03.2022
Пролог: поиск списка, не удовлетворяющего цели
Если у меня есть список ребер для такой задачи, как «Покажите мне маршруты из города, который считается опасным, в тот, который считается безопасным», так что...
dangerous(oakland).
safe(portland).
move(rome,plane,portland)....
769 просмотров
schedule
12.11.2022
Отображение обхода графа поиска в глубину C++
Я работаю над обходом графа, который я настроил как класс, используя векторы для хранения вершин и ребер. Я использую поиск в глубину на графике, чтобы показать пути по мере их прохождения, но я хотел бы каким-то образом заставить мой код отображать...
1871 просмотров
schedule
15.11.2023
ошибка в коде, приведенном в книге Скиены для применения dfs для поиска цикла в графе
Это код для dfs.
bool processed[MAXV+1]; /* which vertices have been processed */
bool discovered[MAXV+1]; /* which vertices have been found */
int parent[MAXV+1]; /* discovery relation */
#define MAXV 1000 /* maximum number of vertices */...
878 просмотров
schedule
16.07.2023
Матрица смежности - ›Направленный граф -› DFS
Это код, который мы с друзьями придумали после того, как возились. То, что мы пытаемся сделать, это прочитать матрицу смежности (input.txt), а затем создать из нее ориентированный граф, чтобы мы могли выполнять поиск с помощью поиска в глубину. Мы...
2410 просмотров
schedule
13.03.2023
открытый лабиринт - поиск в глубину
У меня есть открытый лабиринт с начальной и конечной точками. Я написал алгоритм поиска BFS и DFS для решения лабиринта. Мой BFS находит кратчайшее решение, но мой DFS (который идет вниз, влево, вверх, вправо) создает зигзаг в качестве решения. Это...
1013 просмотров
schedule
21.07.2023
Поиск в глубину дерева с более чем двумя дочерними узлами в Java
У меня есть приложение с древовидной структурой, в которой каждый родитель имеет 3 или более дочерних узла. Каждый узел содержит целочисленное значение. Я пытаюсь увидеть, присутствует ли заданное целочисленное значение в дереве. Как выполнить...
7130 просмотров
schedule
24.05.2024
Является ли время выполнения BFS и DFS на двоичном дереве O (N)?
Я понимаю, что время выполнения BFS и DFS на универсальном графе составляет O (n + m), где n — количество узлов, а m — количество ребер, и это связано с тем, что для каждого узла необходимо учитывать его список смежности. Однако каково время...
21802 просмотров
schedule
08.05.2022
Фермер, волк, коза и капуста Поиск в ширину и в глубину в Java
Итак, я начал эту задачу, где я должен перевезти капусту, волка и козу через реку, не оставляя капусту с козой или волка и козу поодиночке на одной стороне.
Я начал и сильно запутался в том, как подойти к этому. По сути, я думал добавить кучу...
3326 просмотров
schedule
15.12.2022
Поиск в глубину (DFS) в mysql или sqlite
Я ищу способ реализовать алгоритм поиска в глубину в mysql или sqlite
структура таблицы в этом формате
id | node1 | node2
--------------------
1 | 1 | 1
2 | 1 | 2
3 | 1 | 3
4 | 1 | 4
5 | 2 | 3
6 | 2...
606 просмотров
schedule
16.06.2023
Рекурсивный DFS против итеративного DFS
Я пытаюсь понять разницу между рекурсивной DFS и итеративной DFS. Использует ли тот, у кого есть стек, итеративный или рекурсивный подход?
Например, каковы будут результаты использования рекурсивного обхода графа в поиске в глубину и итеративного...
16236 просмотров
schedule
19.03.2022
Подсчитать количество путей в сетке с помощью динамического программирования?
Робот сидит в верхнем левом углу сетки NxN. Робот может двигаться только в двух направлениях: вправо и вниз , где некоторые из ячеек мертвы, т.е. робот не может войти в эту ячейку. Сколько возможных путей есть для робота? Это можно решить с...
4486 просмотров
schedule
04.05.2022
