Realizar amplitud Primero Buscar de forma recursiva

Question

Digamos que desea implementar una búsqueda de ancho de un árbol binario recursivamente. ¿Cómo lo harías?

¿Es posible usar solo la pila de llamadas como almacenamiento auxiliar?

Answer 1

(Asumo que esto es sólo una especie de ejercicio de pensamiento, o incluso una pregunta con trampa tareas/entrevista, pero supongo que podría imaginar alguna extraña escenario donde no se le permite ningún espacio de pila por algún motivo [algún administrador de memoria personalizado realmente malo? algunos problemas de tiempo de ejecución/OS extraños?] mientras todavía tiene acceso a la pila ...)

Cruce de primer ancho tradicionalmente usa una cola, no una pila. La naturaleza de una cola y una pila son bastante opuestas, por lo que tratar de usar la pila de llamadas (que es una pila, de ahí el nombre) como almacenamiento auxiliar (una cola) está condenado al fracaso, a menos que esté haciendo algo estúpidamente ridículo con la pila de llamadas que no deberías ser.

En el mismo token, la naturaleza de cualquier recursión sin cola que intente implementar es esencialmente agregar una pila al algoritmo. Esto hace que ya no sea la primera búsqueda de ancho en un árbol binario, y por lo tanto, el tiempo de ejecución y otras cosas para BFS tradicional ya no se aplican por completo. Por supuesto, siempre puede convertir trivialmente cualquier bucle en una llamada recursiva, pero eso no es ningún tipo de recursión significativa.

Sin embargo, hay formas, como lo han demostrado otros, de implementar algo que sigue la semántica de BFS a algún costo. Si el costo de comparación es costoso, pero el cruce de nodos es barato, como lo hizo @Simon Buchan, simplemente puede ejecutar una búsqueda iterativa en profundidad, solo procesando las hojas. Esto significa que no hay una cola de crecimiento almacenada en el montón, solo una variable de profundidad local, y las pilas se acumulan una y otra vez en la pila de llamadas a medida que el árbol se recorre una y otra vez. Y como se notó en @Patrick, un árbol binario respaldado por una matriz generalmente se almacena en orden transversal primero, de todos modos, por lo que una búsqueda de amplitud en esa sería trivial, también sin necesidad de una cola auxiliar.

Answer 2

No he podido encontrar una manera de hacerlo completamente recursivo (sin ninguna estructura de datos auxiliar). Pero si la cola Q se pasa por referencia, a continuación, puede tener la siguiente función recursiva cola tonta:

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

    BFS(Q) 
} 

Answer 3

Si utiliza una matriz para respaldar el árbol binario, se puede determinar el siguiente nodo algebraicamente. si i es un nodo, sus hijos se pueden encontrar en 2i + 1 (para el nodo izquierdo) y 2i + 2 (para el nodo derecho). vecino de un nodo está dada por i + 1, a menos que i es una potencia de 2

Aquí está pseudocódigo para una implementación muy ingenua de búsqueda en anchura en un árbol de búsqueda binaria gama respaldo. Esto supone una matriz de tamaño fijo y, por lo tanto, un árbol de profundidad fija. Verá los nodos parentless, y podría crear una pila inmanejablemente grande.

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 4

La manera tonta:

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 5

Tuve que implementar un recorrido en heap que salga en un orden BFS. En realidad, no es BFS, pero cumple la misma tarea.

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

Answer 6

El siguiente método utiliza un algoritmo de DFS para obtener todos los nodos en una profundidad particular - que es igual que hacer BFS para ese nivel. Si descubres la profundidad del árbol y haces esto para todos los niveles, los resultados serán los mismos que para un 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); 

Encontrar la profundidad de un árbol es un pedazo de pastel.

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

Answer 7

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

Answer 8

Sea V el vértice a partir

Sea G el gráfico en cuestión

El siguiente es el pseudo código sin usar cola

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) 

Answer 9

Así es un pitón implementación:

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) 

Answer 10

Encontré un algoritmo recursivo muy bueno (incluso funcional) relacionado con el ancho Breadth-First. No es mi idea, pero creo que debería mencionarse en este tema.

Chris Okasaki explica su algoritmo de numeración de ancho de ICFP 2000 en http://okasaki.blogspot.de/2008/07/breadth-first-numbering-algorithm-in.html muy claramente con solo 3 imágenes.

La aplicación Scala de Debasish Ghosh, que he encontrado en http://debasishg.blogspot.de/2008/09/breadth-first-numbering-okasakis.html, es decir:

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 11

Aquí es una implementación recursiva de Scala 2.11.4 BFS. He sacrificado la optimización de la cola de llamadas para abreviar, pero la versión de TCOd es muy similar. Ver también la publicación de @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 12

Aquí hay una implementación de JavaScript que simula Breadth First Traversal con profundidad Primera recursión. Estoy almacenando los valores de nodo en cada profundidad dentro de una matriz, dentro de un hash. Si ya existe un nivel (tenemos una colisión), entonces simplemente empujamos hacia la matriz en ese nivel. También podría usar una matriz en lugar de un objeto JavaScript, ya que nuestros niveles son numéricos y pueden servir como índices de matriz. Puedes devolver nodos, valores, convertir a una lista vinculada o lo que quieras. Solo estoy devolviendo valores por simplicidad.

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 ] } */ 

Aquí es un ejemplo de verdadera amplitud Primera Transversal utilizando un enfoque iterativo.

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 

Answer 13

Un BFS simple y recursividad DFS en Java:
Just Push/ofrecen el nodo raíz del árbol de la pila/cola y llamar a estas funciones.

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 14

Lo siguiente me parece muy natural, usando Haskell.Iterar recursivamente sobre niveles del árbol (aquí colecciono nombres en una cadena ordenada grande como para mostrar el camino a través del árbol):

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 15

siguiente es el código de la aplicación por completo recursiva de amplitud de primera busca de una gráfico bidireccional sin usar bucle y cola.

 

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