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

если вы используете массив для поддержки двоичного дерева, вы можете определить следующий узел алгебраически. если 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)        

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

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

     BFS(Q)
}

следующий метод использовал алгоритм 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;
    }
}

простая рекурсия 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);
}

тупой путь:

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;
}

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

Крис Окасаки объясняет свой алгоритм нумерации широты от 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
}

вот реализация 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)

вот 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]
}

следующее кажется мне довольно естественным, используя 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])

мне пришлось реализовать обход кучи, который выводится в порядке BFS. На самом деле это не BFS, но выполняет ту же задачу.

private void getNodeValue(Node node, int index, int[] array) {
    array[index] = node.value;
    index = (index*2)+1;

    Node left = node.leftNode;
    if (left!=null) getNodeValue(left,index,array);
    Node right = node.rightNode;
    if (right!=null) getNodeValue(right,index+1,array);
}

public int[] getHeap() {
    int[] nodes = new int[size];
    getNodeValue(root,0,nodes);
    return nodes;
}

пусть v-начальная вершина

пусть G-рассматриваемый граф

ниже приведен псевдокод без использования queue

Initially label v as visited as you start from v
BFS(G,v)
    for all adjacent vertices w of v in G:
        if vertex w is not visited:
            label w as visited
    for all adjacent vertices w of v in G:
        recursively call BFS(G,w)

BFS для двоичного (или n-ary) дерева можно сделать рекурсивно без очередей следующим образом (здесь в Java):

public class BreathFirst {

    static class Node {
        Node(int value) {
            this(value, 0);
        }
        Node(int value, int nChildren) {
            this.value = value;
            this.children = new Node[nChildren];
        }
        int value;
        Node[] children;
    }

    static void breathFirst(Node root, Consumer<? super Node> printer) {
        boolean keepGoing = true;
        for (int level = 0; keepGoing; level++) {
            keepGoing = breathFirst(root, printer, level);
        }
    }

    static boolean breathFirst(Node node, Consumer<? super Node> printer, int depth) {
        if (depth < 0 || node == null) return false;
        if (depth == 0) {
            printer.accept(node);
            return true;
        }
        boolean any = false;
        for (final Node child : node.children) {
            any |= breathFirst(child, printer, depth - 1);
        }
        return any;
    }
}

пример обхода печати чисел 1-12 в порядке возрастания:

public static void main(String... args) {
    //            1
    //          / | \
    //        2   3   4
    //      / |       | \
    //    5   6       7  8
    //  / |           | \
    // 9  10         11  12

    Node root = new Node(1, 3);
    root.children[0] = new Node(2, 2);
    root.children[1] = new Node(3);
    root.children[2] = new Node(4, 2);
    root.children[0].children[0] = new Node(5, 2);
    root.children[0].children[1] = new Node(6);
    root.children[2].children[0] = new Node(7, 2);
    root.children[2].children[1] = new Node(8);
    root.children[0].children[0].children[0] = new Node(9);
    root.children[0].children[0].children[1] = new Node(10);
    root.children[2].children[0].children[0] = new Node(11);
    root.children[2].children[0].children[1] = new Node(12);

    breathFirst(root, n -> System.out.println(n.value));
}

#include <bits/stdc++.h>
using namespace std;
#define Max 1000

vector <int> adj[Max];
bool visited[Max];

void bfs_recursion_utils(queue<int>& Q) {
    while(!Q.empty()) {
        int u = Q.front();
        visited[u] = true;
        cout << u << endl;
        Q.pop();
        for(int i = 0; i < (int)adj[u].size(); ++i) {
            int v = adj[u][i];
            if(!visited[v])
                Q.push(v), visited[v] = true;
        }
        bfs_recursion_utils(Q);
    }
}

void bfs_recursion(int source, queue <int>& Q) {
    memset(visited, false, sizeof visited);
    Q.push(source);
    bfs_recursion_utils(Q);
}

int main(void) {
    queue <int> Q;
    adj[1].push_back(2);
    adj[1].push_back(3);
    adj[1].push_back(4);

    adj[2].push_back(5);
    adj[2].push_back(6);

    adj[3].push_back(7);

    bfs_recursion(1, Q);
    return 0;
}

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

BinarySearchTree.prototype.breadthFirstRec = function() {

    var levels = {};

    var traverse = function(current, depth) {
        if (!current) return null;
        if (!levels[depth]) levels[depth] = [current.value];
        else levels[depth].push(current.value);
        traverse(current.left, depth + 1);
        traverse(current.right, depth + 1);
    };

    traverse(this.root, 0);
    return levels;
};


var bst = new BinarySearchTree();
bst.add(20, 22, 8, 4, 12, 10, 14, 24);
console.log('Recursive Breadth First: ', bst.breadthFirstRec());
/*Recursive Breadth First:  
{ '0': [ 20 ],
  '1': [ 8, 22 ],
  '2': [ 4, 12, 24 ],
  '3': [ 10, 14 ] } */

вот пример фактического первого обхода ширины с использованием итерационного подхода.

BinarySearchTree.prototype.breadthFirst = function() {

    var result = '',
        queue = [],
        current = this.root;

    if (!current) return null;
    queue.push(current);

    while (current = queue.shift()) {
        result += current.value + ' ';
        current.left && queue.push(current.left);
        current.right && queue.push(current.right);
    }
    return result;
};

console.log('Breadth First: ', bst.breadthFirst());
//Breadth First:  20 8 22 4 12 24 10 14

Ниже приведен мой код для полностью рекурсивной реализации широтно-первого поиска двунаправленного графа без использования цикла и очереди.

public class Graph
{
    public int V;   
    public LinkedList<Integer> adj[];

    Graph(int v)
    {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList<>();
    }

    void addEdge(int v,int w)
    {
        adj[v].add(w);
        adj[w].add(v);
    }

    public LinkedList<Integer> getAdjVerted(int vertex)
    {
        return adj[vertex];
    }

    public String toString()
    {
        String s = "";

        for (int i=0;i<adj.length;i++)
        {
            s = s +"\n"+i +"-->"+ adj[i] ;
        }
        return s;
    }
}

//BFS IMPLEMENTATION

public static void recursiveBFS(Graph graph, int vertex,boolean visited[], boolean isAdjPrinted[])
    {
        if (!visited[vertex])
        {
            System.out.print(vertex +" ");
            visited[vertex] = true;
        }

        if(!isAdjPrinted[vertex])
        {
            isAdjPrinted[vertex] = true;
            List<Integer> adjList = graph.getAdjVerted(vertex);
            printAdjecent(graph, adjList, visited, 0,isAdjPrinted);
        }
    }

    public static void recursiveBFS(Graph graph, List<Integer> vertexList, boolean visited[], int i, boolean isAdjPrinted[])
    {
        if (i < vertexList.size())
        {
            recursiveBFS(graph, vertexList.get(i), visited, isAdjPrinted);
            recursiveBFS(graph, vertexList, visited, i+1, isAdjPrinted);
        }
    }

    public static void printAdjecent(Graph graph, List<Integer> list, boolean visited[], int i, boolean isAdjPrinted[])
    {
        if (i < list.size())
        {
            if (!visited[list.get(i)])
            {
                System.out.print(list.get(i)+" ");
                visited[list.get(i)] = true;
            }
            printAdjecent(graph, list, visited, i+1, isAdjPrinted);
        }
        else
        {
            recursiveBFS(graph, list, visited, 0, isAdjPrinted);
        }
    }