algorithm - recursivas - Realizar la primera búsqueda de forma recursiva
funciones recursivas ejemplos c++ (16)
(Supongo que esto es solo una especie de ejercicio de pensamiento, o incluso una pregunta truco de tarea / entrevista, pero supongo que podría imaginar algún extraño escenario en el que no se permita ningún espacio de montón por alguna razón [alguna muy mala costumbre] administrador de memoria? algunos problemas extraños de tiempo de ejecución / SO?] mientras todavía tienes acceso a la pila ...)
El recorrido transversal de ancho utiliza tradicionalmente 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 anotó @Patrick , un árbol binario respaldado por una matriz generalmente se almacena en orden transversal de amplitud de todos modos, por lo que una búsqueda de amplitud en la que sería trivial, también sin necesidad de una cola auxiliar.
Supongamos 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?
Aquí hay una implementación de JavaScript que simula Breadth First Traversal con profundidad First 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í hay un ejemplo de Breadth First Traversal real 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
Aquí hay una implementación de 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)
Aquí hay una implementación de Scala 2.11.4 de BFS recursiva. 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 @snv 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]
}
BFS para un árbol binario (o n-ario) se puede hacer recursivamente sin colas de la siguiente manera (aquí en 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;
}
}
Un ejemplo de impresión transversal números 1-12 en orden ascendente:
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));
}
Deje v ser el vértice inicial
Deje que G sea el gráfico en cuestión
El siguiente es el pseudo código sin usar la 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)
El siguiente método utilizó un algoritmo DFS para obtener todos los nodos en una profundidad particular, que es lo mismo 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 pan comido.
public int MaxDepth(Tree root)
{
if (root == null)
return 0;
else
return Math.Max(MaxDepth(root.Left), MaxDepth(root.Right)) + 1;
}
Encontré un algoritmo recursivo muy atractivo (incluso funcional) relacionado con el ancho de banda ancha. 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 implementación de Scala de Debasish Ghosh, que encontré en http://debasishg.blogspot.de/2008/09/breadth-first-numbering-okasakis.html , es:
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
}
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;
}
Lo siguiente me parece muy natural, usando Haskell. Iterare recursivamente sobre los niveles del árbol (aquí recojo los nombres en una cadena grande ordenada 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])
No pude encontrar una manera de hacerlo completamente recursivo (sin ninguna estructura de datos auxiliar). Pero si la cola Q se pasa por referencia, entonces puede tener la siguiente función recursiva tonta:
BFS(Q)
{
if (|Q| > 0)
v <- Dequeue(Q)
Traverse(v)
foreach w in children(v)
Enqueue(Q, w)
BFS(Q)
}
Tuve que implementar un cruce de montón que se genera 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;
}
Una simple recursión BFS y DFS en Java:
Simplemente presione / ofrezca el nodo raíz del árbol en la pila / cola y llame 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);
}
A continuación está mi código para la implementación completamente recursiva de la búsqueda de ancho de un 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);
}
}
Si usa una matriz para respaldar el árbol binario, puede determinar el siguiente nodo algebraicamente. si i soy un nodo, entonces sus hijos pueden encontrarse en 2i + 1 (para el nodo izquierdo) y 2i + 2 (para el nodo derecho). El siguiente vecino de un nodo viene dado por i + 1 , a menos que i tenga una potencia de 2
Aquí hay un pseudocódigo para una implementación muy ingenua de la primera búsqueda de amplitud en un árbol de búsqueda binario respaldado por una matriz. 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)
#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;
}