Вопросы с тегом «graph-traversal»

Вопросы об алгоритмах обхода графов, таких как BFS и DFS.

79
Поиск по графику: сначала ширина, либо глубина

При поиске графиков существует два простых алгоритма: ширина в ширину и глубина вначале (обычно это делается путем добавления всех соседних узлов графа в очередь (ширина в первую очередь) или в стек (глубина в первую очередь)). Есть ли преимущества одного над другим? Те, о которых я мог думать:...

28
Алгоритм определения диаметра дерева с использованием BFS / DFS. Почему это работает?

Эта ссылка предоставляет алгоритм для определения диаметра ненаправленного дерева с использованием BFS / DFS . Подводя итог: Запустите BFS на любом узле в графе, помня узел, который вы обнаружили последним. Запустите BFS, вспомнив последний обнаруженный узел v. d (u, v) - диаметр дерева. Почему это...

19
Назначение серого узла в графе поиска в глубину

Во многих реализациях поиска в глубину, который я видел (например: здесь ), код различает серую вершину (обнаружена, но не все ее соседи были посещены) и черную вершину (обнаружена и все ее соседи посещены) , Какова цель этого различия? Кажется, что алгоритм DFS никогда не посещает посещенную...

14
Кратчайший непересекающийся путь для графа, вложенного в евклидову плоскость (2D)

Какой алгоритм вы бы использовали, чтобы найти кратчайший путь графа, который вложен в евклидову плоскость, чтобы путь не содержал каких-либо самопересечений (во вложении)? Например, на графике ниже вы хотите перейти от . Обычно такой алгоритм, как алгоритм Дейкстры, выдает такую...

14
Шаги, которые гарантируют выход из лабиринта

Имеется двухмерный лабиринт, где вы можете дать 4 команды «двигаться вверх / вниз / вправо / влево». Зная лабиринт, а не где находится человек, как найти минимальную последовательность команд, которая гарантирует выход из лабиринта? Я ищу единственную последовательность команд, которая будет...

13
Количество возможных путей поиска при поиске в BST

У меня есть следующий вопрос, но у меня нет ответа на этот вопрос. Буду признателен, если мой метод правильный: Q. При поиске значения ключа 60 в двоичном дереве поиска узлы, содержащие значения ключа 10, 20, 40, 50, 70, 80, 90, пересекаются, необязательно в указанном порядке. Сколько возможных...

11
Графики, которые заставляют DFS и BFS обрабатывать узлы в одном и том же порядке

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

11
Разница между поперечными и передними кромками в DFT

В глубине первого дерева есть ребра, определяющие дерево (то есть ребра, которые использовались при обходе). Есть некоторые оставшиеся ребра, соединяющие некоторые другие узлы. В чем разница между поперечной кромкой и передней кромкой? Из википедии: Основываясь на этом остовном дереве, ребра...

11
Почему считается, что DFS имеет сложность ?

Согласно этим примечаниям считается , что DFS имеет сложность пространства , где - коэффициент ветвления дерева, а - максимальная длина любого пути в пространстве состояний.б мO ( б м )O(bm)O(bm)бbbмmm То же самое сказано в этой странице Wikibook на Неинформированном Поиске . Теперь «инфобокс»...

11
Что означает «ширина» в поиске ширины?

Я узнавал о широте первого поиска и вопрос пришел в голову , что , почему BFS называется так. В книге Введение в алгоритмы по КСПС , я прочитал следующую причину этого: Поиск в ширину так назван потому, что он расширяет границы между открывшимся и неоткрытых вершин равномерно по всей ширине...

11
Может ли предварительный заказ двух разных деревьев быть одинаковыми, даже если они разные?

Эта вопрос в значительной степени объясняет, что они могут, но не показывает никаких примеров наличия двух разных деревьев с одним и тем же обходом предварительного заказа. Также упоминается, что обход по порядку двух разных деревьев может быть одинаковым, хотя они структурно разные. Есть ли пример...

9
Уникальный путь в ориентированном графе

Я разрабатываю алгоритм для класса, который будет определять, является ли ориентированный граф уникальным по отношению к вершине , так что для любого существует не более одного пути от до . Я начал с использования BFS (поиск в ширину), чтобы найти кратчайший путь от v до другой вершины u, а затем...

9
Нахождение k-кратчайшего пути между двумя узлами

Учитывая взвешенный орграф и весовую функцию , обычно можно использовать алгоритм Дейкстры для получения кратчайшего пути. Что меня интересует, так это как получить -короткий путь, -короткий путь и так далее.G = V, Eгзнак равноВ,ЕG=V,Ed( U , V )d(U,v)d(u,v)2н д2Nd2^{nd}3г д3рd3^{rd} Вопросов:...