Лучшие depth-first-search вопросы ИТ разработчиков

  • 2голосов
  • 4ответа
  • 0просмотров

Любая альтернатива (очень медленной) глубокой копии в DFS?

У меня есть хороший граф (список), содержащий 81 вершины (каждая вершина является экземпляром класса Vertex). Каждая вершина имеет 20 соседей. Каждая вершина имеет ряд возможных значений (в диапазоне от 1 до 9), которые, учитывая некоторые ...

Задан Apr 13, 2012, 10:23 AMотluke14free
  • 4голосов
  • 4ответа
  • 0просмотров

Уплощенная в глубину коллекция объектов иерархии с использованием LINQ

У меня есть иерархия объектов (MasterNode -> ChildNodes), где главный и дочерний узлы имеют одинаковый тип, и есть только два уровня (верхний уровень и дочерние), как этот («A» является родителем D, E и F). , 'B' является родителем G и т. ...

Задан Sep 03, 2012, 8:22 AMотThanasis Ioannidis
  • 4голосов
  • 4ответа
  • 0просмотров

Уплощенная в глубину коллекция объектов иерархии с использованием LINQ

У меня есть иерархия объектов (MasterNode -> ChildNodes), где главный и дочерний узлы имеют одинаковый тип, и есть только два уровня (верхний уровень и дочерние узлы), как это ('A') является родителем D, E и F, 'B' является родителем G и ...

Задан Sep 03, 2012, 5:30 AMотThanasis Ioannidis
  • 9голосов
  • 3ответа
  • 0просмотров

Функциональный стиль раннего выхода из глубины рекурсии

У меня есть вопрос о написании рекурсивных алгоритмов в функциональном стиле. Я буду использовать Scala для моего примера здесь, но этот вопрос относится к любому функциональному языку. Я делаю перечисление в глубину-дерево, где каждый узел ...

Задан Nov 20, 2012, 10:22 PMотW.P. McNeill
  • 9голос
  • 1ответ
  • 0просмотров

Топологическая сортировка, чтобы найти количество путей к т

Мне нужно разработать алгоритм O (| V | + | E |), связанный с топологической сортировкой, который в ориентированном ациклическом графе (DAG) определяет число путей от каждой вершины графа до t (t - это узел с out-степень 0). Я ...

Задан Aug 06, 2013, 4:17 PMотStratford
  • 3голосов
  • 4ответа
  • 0просмотров

Сложность поиска всех простых путей с использованием поиска в глубину?

Спасибо всем, кто отвечает идеями и альтернативными решениями. Всегда приветствуются более эффективные способы решения проблем, а также напоминания о моих предположениях. Тем не менее, яЯ хотел бы, чтобы вы на мгновение проигнорировали, какая у ...

Задан Dec 02, 2009, 3:12 AMотhexium
  • 4голос
  • 1ответ
  • 0просмотров

JavaScript Поиск в глубину

Я пытаюсь реализовать DFS в JavaScript, но у меня возникла небольшая проблема. Вот мой класс Алгоритм: "use strict"; define([], function () { return function () { var that = this; this.search = function (searchFor, node) { if (searchFor === ...

Задан Oct 12, 2013, 6:39 PMотRichard Knop
  • 9голосов
  • 2ответа
  • 0просмотров

Является ли время выполнения BFS и DFS в двоичном дереве O (N)?

Я понимаю, что время выполнения BFS и DFS на общем графе равно O (n + m), где n - количество узлов, а m - количество ребер, и это потому, что для каждого узла должен рассматриваться его список смежности. Однако, какова среда выполнения BFS и DFS, ...

Задан Nov 11, 2013, 7:16 AMотgmemon
  • 10голосов
  • 5ответов
  • 0просмотров

Топологическая сортировка с использованием DFS без рекурсии

Я знаю, что обычный метод топологической сортировки - это использование DFS с рекурсией. Но как бы вы сделали это, используяstack вместо рекурсии? Мне нужно получить обратный пост-заказ, но яя вроде застрял: График являетсяvector > список ...

Задан Nov 22, 2013, 7:01 PMотfersarr
  • 19голосов
  • 3ответа
  • 0просмотров

Почему поиск в глубину считается эффективным с точки зрения пространства?

В курсе алгоритмов яберу, этоСказал, чтопоиск в глубину(DFS) гораздо более компактно, чемпоиск в ширину(BFS). Это почему? Хотя в основном они делают то же самое, в DFS мыповторное наложение текущего узлапреемники в то время как в BFS мывновь ...

Задан Dec 06, 2013, 3:52 PMотHSN
  • 4голосов
  • 4ответа
  • 0просмотров

Поиск в глубину в Python

я пытаюсь сделать поиск в глубину в Python, но этоне работает. В основном у нас есть доска для пасьянсов: 1 ' [1,1,1,1,1,0,1,1,1,1]s представляет колышек, а 0 - открытое пятно. Вы должны перемещать колышек по одному ДВУХ СЛОТОВ назад или вперед ...

Задан Jan 26, 2010, 5:00 AMотy2k
  • 27голосов
  • 13ответов
  • 0просмотров

Как реализовать поиск по глубине для графа с нерекурсивным приближением

Ну, я потратил много времени на эту проблему. Тем не менее, я могу только найти решения с нерекурсивными методами для дерева:Не рекурсивно для дерева [https://stackoverflow.com/questions/5278580/non-recursive-depth-first-search-algorithm] или ...

Задан Feb 02, 2014, 7:58 AMотAlston
  • 21голосов
  • 3ответа
  • 0просмотров

Является ли обход предварительного заказа в двоичном дереве таким же, как поиск в глубину?

Мне кажется, что обход по предварительному заказу и DFS такие же, как в обоих случаях, когда мы проходим до конечного узла в глубине. Может ли кто-нибудь поправить меня, если я ошибаюсь? Заранее спасибо!

Задан Feb 05, 2014, 8:08 AMотSrikanth Kandalam
  • 2голос
  • 1ответ
  • 0просмотров

Как использовать DFS на массиве

У меня есть одномерный список значений, это выглядит как "int [] values ​​'". Я полагаю, что я преобразовал его в 2D-список, как это: for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { board[i][j] = values[i * 4 + j]; } }Доска - это ...

Задан Mar 16, 2014, 11:44 PMотuser2835532
  • 3голосов
  • 3ответа
  • 0просмотров

Алгоритм Дейкстры с «обязательными для прохождения» узлами

Я пытаюсь реализовать алгоритм Дейкстры, который может найти кратчайший путь между начальным узлом и конечным узлом. До достижения конечного узла есть несколько промежуточных узлов, которые необходимо пропустить (более одного), например, 2 или 3 ...

Задан Aug 18, 2014, 5:19 PMотuser3778610
  • 8голосов
  • 2ответа
  • 0просмотров

Какая польза от использования 3 состояний для вершины в DFS?

В объяснении поиска в глубину (DFS) вАлгоритмы в двух словах (2-е издание)автор использовал 3 состояния для вершины, скажембелый(не посещал),серый(не посещал соседей),черный(Посетили). [/imgs/Hnv2i.png] Два состояния (белыйа такжечерный) ...

Задан Aug 13, 2016, 4:41 PMотnn0p
  • 7голосов
  • 2ответа
  • 0просмотров

алгоритм перечисления всех возможных путей

Рассмотрим следующий график: Я пытаюсь найти способ перечислить все возможные пути от исходного узла до целевого узла. Например, от А до Е у нас есть следующие возможные пути: A B C D E A B C E A C D E A C EОбратите внимание, что для A C D E ...

Задан Oct 12, 2010, 12:48 PMотdcp
  • 23голосов
  • 2ответа
  • 0просмотров

Как пройти циклически ориентированные графы с модифицированным алгоритмом DFS

ОБЗОР Я пытаюсь понять, как пройтиориентированные циклические графыиспользуя какой-то итерационный алгоритм DFS. Вот небольшая версия mcve того, что я сейчас реализовал (она не имеет дело с циклами): class Node(object): def __init__(self, ...

Задан Sep 10, 2016, 3:34 PMотBPL
Пред1След