Esecuzione di ricerca in ampiezza in modo ricorsivo
https://stackoverflow.com/questions/2549541
-
23-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Diciamo che si voleva attuare una ricerca in ampiezza di un albero binario ricorsivamente . Come si va su di esso?
E 'possibile utilizzando solo il call-stack come memoria ausiliaria?
Soluzione
(sto supponendo che questo è solo una sorta di esercizio di pensiero, o anche una domanda compiti a casa / intervista trucco, ma suppongo che avrei potuto immaginare un bizzarro scenario in cui non ti è permesso alcun spazio heap per qualche ragione [un po ' davvero male gestore di memoria personalizzato? qualche bizzarra runtime / problemi di OS?], mentre è sempre possibile accedere alla pila ...)
attraversamento in ampiezza utilizza tradizionalmente una coda, non una pila. La natura di una coda e uno stack sono praticamente opposto, in modo cercando di utilizzare lo stack di chiamate (che è una pila, da cui il nome) come memoria ausiliaria (una coda) è praticamente destinato al fallimento, a meno che non si sta facendo qualcosa di stupidamente ridicolo con lo stack di chiamate che non si deve essere.
Sulla stessa ragione, la natura di qualsiasi ricorsione non coda si tenta di implementare è essenzialmente l'aggiunta di una pila per l'algoritmo. Questo lo rende ampiezza non è più prima ricerca su un albero binario, e quindi il run-time e quant'altro per i tradizionali BFS non è più completamente applicare. Naturalmente, si può sempre banalmente trasformare qualsiasi ciclo in una chiamata ricorsiva, ma che non è alcun tipo di ricorsione significativa.
Tuttavia, ci sono modi, come dimostrato da altri, per realizzare qualcosa che segue la semantica di BFS ad un certo costo. Se il costo del confronto è costoso, ma nodo attraversamento è economico, poi come @Simon Buchan ha fatto, si può semplicemente eseguire una ricerca in profondità iterativo, solo lavorazione delle foglie. Ciò significherebbe nessuna coda cresce memorizzati nel mucchio, a profondità variabile locale e pile di essere costruito più e più volte sul stack di chiamate come l'albero viene attraversato più e più volte. E come @Patrick notato, un albero binario sostenuta da un array è generalmente memorizzati in ampiezza ordine di attraversamento comunque, quindi una ricerca in ampiezza su tale sarebbe banale, anche senza bisogno di una coda ausiliario.
Altri suggerimenti
Se si utilizza una matrice per eseguire l'albero binario, è possibile determinare il nodo successivo algebricamente. se i è un nodo, allora i suoi figli possono essere trovati a 2i + 1 (per il nodo di sinistra) e 2i + 2 (per il nodo a destra). vicino di casa di un nodo è dato da i + 1, a meno che non i è una potenza di 2
Ecco pseudocodice per un'implementazione molto ingenuo di ricerca in ampiezza su un albero binario di ricerca di matrice backed. Questa assume una disposizione fissa dimensioni e quindi un albero profondità fissa. Essa esaminerà nodi senza genitori, e potrebbe creare un ingestibile grande pila.
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)
non riuscivo a trovare un modo per farlo completamente ricorsiva (senza dati-struttura ausiliaria). Ma se la coda Q è passato per riferimento, allora si può avere la seguente funzione ricorsiva sciocco coda:
BFS(Q)
{
if (|Q| > 0)
v <- Dequeue(Q)
Traverse(v)
foreach w in children(v)
Enqueue(Q, w)
BFS(Q)
}
Il seguente metodo utilizzato un algoritmo di DFS per ottenere tutti i nodi in una particolare profondità - che è lo stesso di fare BFS per quel livello. Se si scopre profondità dell'albero e fare questo per tutti i livelli, i risultati saranno stessa di una 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);
}
profondità Ritrovamento di un albero è un pezzo di torta:
public int MaxDepth(Tree root) {
if (root == null) {
return 0;
} else {
return Math.Max(MaxDepth(root.Left), MaxDepth(root.Right)) + 1;
}
}
Un semplice BFS e ricorsione DFS in Java:
Basta premere / offrono il nodo radice dell'albero nella pila / coda e chiamano queste funzioni.
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);
}
Il modo muto:
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;
}
Ho trovato un bellissimo ricorsivo algoritmo (anche funzionale) in ampiezza relativi attraversamento. Non la mia idea, ma penso che dovrebbe essere menzionato in questo argomento.
Chris Okasaki spiega il suo algoritmo di ampiezza numerazione da ICFP 2000 http://okasaki.blogspot.de/2008/07/breadth-first-numbering-algorithm-in.html molto chiaramente con solo 3 immagini.
L'implementazione Scala di Debasish Ghosh, che ho trovato su 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
}
Ecco un'implementazione di 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)
Ecco un'implementazione Scala 2.11.4 di ricorsiva BFS. Ho sacrificato ottimizzazione tail-call per brevità, ma la versione TCOd è molto simile. Vedi anche @snv postale 's .
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]
}
Di seguito sembra abbastanza naturale per me, utilizzando Haskell. Iterare ricorsivamente rispetto ai livelli degli alberi (qui raccolgo i nomi in un grande stringa ordinato di mostrare il percorso attraverso l'albero):
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])
Ecco breve Scala soluzione:
def bfs(nodes: List[Node]): List[Node] = {
if (nodes.nonEmpty) {
nodes ++ bfs(nodes.flatMap(_.children))
} else {
List.empty
}
}
Idea di utilizzando come valore di ritorno dell'accumulatore è particolarmente adatto. Può essere implementato in altre lingue in modo simile, basta assicurarsi che il processo di funzione ricorsiva elenco dei nodi .
Codice di prova messa in vendita (utilizzando @marco albero di test):
import org.scalatest.FlatSpec
import scala.collection.mutable
class Node(val value: Int) {
private val _children: mutable.ArrayBuffer[Node] = mutable.ArrayBuffer.empty
def add(child: Node): Unit = _children += child
def children = _children.toList
override def toString: String = s"$value"
}
class BfsTestScala extends FlatSpec {
// 1
// / | \
// 2 3 4
// / | | \
// 5 6 7 8
// / | | \
// 9 10 11 12
def tree(): Node = {
val root = new Node(1)
root.add(new Node(2))
root.add(new Node(3))
root.add(new Node(4))
root.children(0).add(new Node(5))
root.children(0).add(new Node(6))
root.children(2).add(new Node(7))
root.children(2).add(new Node(8))
root.children(0).children(0).add(new Node(9))
root.children(0).children(0).add(new Node(10))
root.children(2).children(0).add(new Node(11))
root.children(2).children(0).add(new Node(12))
root
}
def bfs(nodes: List[Node]): List[Node] = {
if (nodes.nonEmpty) {
nodes ++ bfs(nodes.flatMap(_.children))
} else {
List.empty
}
}
"BFS" should "work" in {
println(bfs(List(tree())))
}
}
Output:
List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
ho dovuto implementare un attraversamento mucchio che emette in un ordine BFS. Non è in realtà BFS, ma compie la stessa operazione.
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;
}
Sia v il vertice iniziale
Sia G il grafico in questione
Quello che segue è il codice pseudo senza utilizzare coda
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 per una binaria (o n-ario) albero può essere fatto in modo ricorsivo senza code come segue (qui in 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 esempio la stampa di numeri traversal 1-12 in ordine crescente:
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;
}
Ecco un'implementazione JavaScript che finge Larghezza Prima Traversal con profondità First ricorsione. Sto memorizzare i valori del nodo a ciascuna profondità all'interno di una matrice, all'interno di un hash. Se un livello esiste già (abbiamo una collisione), quindi abbiamo solo spingere alla matrice a quel livello. Si potrebbe usare un array invece di un oggetto JavaScript pure poiché i nostri livelli sono numerici e possono servire come indici di array. È possibile restituire i nodi, i valori, convertire in una lista collegata, o quello che volete. Sto solo la restituzione di valori per motivi di semplicità.
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 ] } */
Ecco un esempio di reale Larghezza Prima Traversal utilizzando un approccio 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
In seguito è il mio codice per tutto ricorsiva implementazione di breadth-first-ricerca di un grafico bidirezionale senza l'utilizzo di loop e coda.
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);
}
}
Ecco un'implementazione ricorsiva attraversamento di Python BFS, lavorando per un grafico con nessun ciclo.
def bfs_recursive(level):
'''
@params level: List<Node> containing the node for a specific level.
'''
next_level = []
for node in level:
print(node.value)
for child_node in node.adjency_list:
next_level.append(child_node)
if len(next_level) != 0:
bfs_recursive(next_level)
class Node:
def __init__(self, value):
self.value = value
self.adjency_list = []
