Выполнение поиска в ширину рекурсивно

Question

Допустим, вы хотели реализовать поиск в двоичном формате в ширину рекурсивно .Как бы вы поступили?

Возможно ли использовать только стек вызовов в качестве вспомогательного хранилища?

Answer 1

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

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

В том же ключе природа любой нехвостовой рекурсии, которую вы пытаетесь реализовать, заключается в добавлении стека в алгоритм. Это больше не позволяет выполнять поиск в двоичном дереве в ширину, и, таким образом, время выполнения и все такое для традиционной BFS больше не применяется полностью. Конечно, вы всегда можете легко превратить любой цикл в рекурсивный вызов, но это не какая-либо значимая рекурсия.

Однако, как продемонстрировали другие, есть способы реализовать что-то, что следует семантике BFS за определенную плату. Если стоимость сравнения стоит дорого, но обход узлов обходится дешево, то, как @ Simon Buchan , вы можете просто запустить итеративный поиск в глубину, только обработав листья. Это будет означать отсутствие растущей очереди, хранящейся в куче, только локальную переменную глубины и многократное наращивание стеков в стеке вызовов при повторном обходе дерева. И, как отмечал @ Patrick , двоичное дерево, поддерживаемое массивом, в любом случае обычно хранится в порядке обхода в ширину, поэтому поиск в ширину в этом случае будет тривиальным, также без необходимости во вспомогательной очереди.

Answer 2

Если вы используете массив для поддержки двоичного дерева, вы можете определить следующий узел алгебраически. если i является узлом, то его дочерние элементы могут быть найдены в 2i + 1 (для левого узла) и 2i + 2 (для правого узла). Следующий сосед узла задается как i + 1, если i не является степенью 2

Вот псевдокод для очень наивной реализации поиска в ширину в двоичном дереве поиска на основе массива. Это предполагает массив фиксированного размера и, следовательно, дерево фиксированной глубины. Он будет смотреть на узлы без родителей и может создать неуправляемо большой стек.

bintree-bfs(bintree, elt, i)
    if (i == LENGTH)
        return false

    else if (bintree[i] == elt)
        return true

    else 
        return bintree-bfs(bintree, elt, i+1)        

Answer 3

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

BFS(Q)
{
  if (|Q| > 0)
     v <- Dequeue(Q)
     Traverse(v)
     foreach w in children(v)
        Enqueue(Q, w)    

     BFS(Q)
}

Answer 4

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

public void PrintLevelNodes(Tree root, int level) {
    if (root != null) {
        if (level == 0) {
            Console.Write(root.Data);
            return;
        }
        PrintLevelNodes(root.Left, level - 1);
        PrintLevelNodes(root.Right, level - 1);
    }
}

for (int i = 0; i < depth; i++) {
    PrintLevelNodes(root, i);
}

Нахождение глубины дерева - это кусок пирога:

public int MaxDepth(Tree root) {
    if (root == null) {
        return 0;
    } else {
        return Math.Max(MaxDepth(root.Left), MaxDepth(root.Right)) + 1;
    }
}

Answer 5

Простая рекурсия BFS и DFS в Java:
Просто нажмите / предложите корневой узел дерева в стеке / очереди и вызовите эти функции.

public static void breadthFirstSearch(Queue queue) {

    if (queue.isEmpty())
        return;

    Node node = (Node) queue.poll();

    System.out.println(node + " ");

    if (node.right != null)
        queue.offer(node.right);

    if (node.left != null)
        queue.offer(node.left);

    breadthFirstSearch(queue);
}

public static void depthFirstSearch(Stack stack) {

    if (stack.isEmpty())
        return;

    Node node = (Node) stack.pop();

    System.out.println(node + " ");

    if (node.right != null)
        stack.push(node.right);

    if (node.left != null)
        stack.push(node.left);

    depthFirstSearch(stack);
}

Answer 6

тупой путь:

template<typename T>
struct Node { Node* left; Node* right; T value; };

template<typename T, typename P>
bool searchNodeDepth(Node<T>* node, Node<T>** result, int depth, P pred) {
    if (!node) return false;
    if (!depth) {
        if (pred(node->value)) {
            *result = node;
        }
        return true;
    }
    --depth;
    searchNodeDepth(node->left, result, depth, pred);
    if (!*result)
        searchNodeDepth(node->right, result, depth, pred);
    return true;
}

template<typename T, typename P>
Node<T>* searchNode(Node<T>* node, P pred) {
    Node<T>* result = NULL;
    int depth = 0;
    while (searchNodeDepth(node, &result, depth, pred) && !result)
        ++depth;
    return result;
}

int main()
{
    // a c   f
    //  b   e
    //    d
    Node<char*>
        a = { NULL, NULL, "A" },
        c = { NULL, NULL, "C" },
        b = { &a, &c, "B" },
        f = { NULL, NULL, "F" },
        e = { NULL, &f, "E" },
        d = { &b, &e, "D" };

    Node<char*>* found = searchNode(&d, [](char* value) -> bool {
        printf("%s\n", value);
        return !strcmp((char*)value, "F");
    });

    printf("found: %s\n", found->value);

    return 0;
}

Answer 7

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

Крис Окасаки объясняет свой алгоритм нумерации в ширину из ICFP 2000 на http://okasaki.blogspot.de/2008/07/breadth-first-numbering-algorithm-in.html очень четко только с 3 фотографиями.

Реализация Scala Debasish Ghosh, которую я нашел в http://debasishg.blogspot.de/2008/09/breadth-first-numbering-okasakis.html,:

trait Tree[+T]
case class Node[+T](data: T, left: Tree[T], right: Tree[T]) extends Tree[T]
case object E extends Tree[Nothing]

def bfsNumForest[T](i: Int, trees: Queue[Tree[T]]): Queue[Tree[Int]] = {
  if (trees.isEmpty) Queue.Empty
  else {
    trees.dequeue match {
      case (E, ts) =>
        bfsNumForest(i, ts).enqueue[Tree[Int]](E)
      case (Node(d, l, r), ts) =>
        val q = ts.enqueue(l, r)
        val qq = bfsNumForest(i+1, q)
        val (bb, qqq) = qq.dequeue
        val (aa, tss) = qqq.dequeue
        tss.enqueue[org.dg.collection.BFSNumber.Tree[Int]](Node(i, aa, bb))
    }
  }
}

def bfsNumTree[T](t: Tree[T]): Tree[Int] = {
  val q = Queue.Empty.enqueue[Tree[T]](t)
  val qq = bfsNumForest(1, q)
  qq.dequeue._1
}

Answer 8

Вот Scala 2.11.4 реализация рекурсивной BFS. Я пожертвовал оптимизацией хвостового вызова для краткости, но версия TCOd очень похожа. Смотрите также @ snv сообщение.

import scala.collection.immutable.Queue

object RecursiveBfs {
  def bfs[A](tree: Tree[A], target: A): Boolean = {
    bfs(Queue(tree), target)
  }

  private def bfs[A](forest: Queue[Tree[A]], target: A): Boolean = {
    forest.dequeueOption exists {
      case (E, tail) => bfs(tail, target)
      case (Node(value, _, _), _) if value == target => true
      case (Node(_, l, r), tail) => bfs(tail.enqueue(List(l, r)), target)
    }
  }

  sealed trait Tree[+A]
  case class Node[+A](data: A, left: Tree[A], right: Tree[A]) extends Tree[A]
  case object E extends Tree[Nothing]
}

Answer 9

Мне кажется, что использование Haskell выглядит довольно естественно. Итеративно выполнять итерацию по уровням дерева (здесь я собираю имена в большую упорядоченную строку, чтобы показать путь через дерево):

data Node = Node {name :: String, children :: [Node]}
aTree = Node "r" [Node "c1" [Node "gc1" [Node "ggc1" []], Node "gc2" []] , Node "c2" [Node "gc3" []], Node "c3" [] ]
breadthFirstOrder x = levelRecurser [x]
    where levelRecurser level = if length level == 0
                                then ""
                                else concat [name node ++ " " | node <- level] ++ levelRecurser (concat [children node | node <- level])

Answer 10

Вот реализация Python:

graph = {'A': ['B', 'C'],
         'B': ['C', 'D'],
         'C': ['D'],
         'D': ['C'],
         'E': ['F'],
         'F': ['C']}

def bfs(paths, goal):
    if not paths:
        raise StopIteration

    new_paths = []
    for path in paths:
        if path[-1] == goal:
            yield path

        last = path[-1]
        for neighbor in graph[last]:
            if neighbor not in path:
                new_paths.append(path + [neighbor])
    yield from bfs(new_paths, goal)


for path in bfs([['A']], 'D'):
    print(path)