Esecuzione della larghezza Prima ricerca in modo ricorsivo

Question

Si supponga di voler implementare una ricerca in larghezza di un albero binario in modo ricorsivo. Come faresti a riguardo?

È possibile utilizzare solo lo stack di chiamata come memoria ausiliaria?

Answer 1

(sto supponendo che questo è solo una sorta di esercizio di pensiero, o anche una domanda trabocchetto compiti a casa/intervista, ma suppongo che potrei immaginare qualche bizzarro scenario in cui non è consentito alcun spazio nell'heap per qualche motivo [alcuni veramente brutti gestori di memoria personalizzati? alcuni bizzarri problemi di runtime/OS?] mentre hai ancora accesso allo stack ...)

Larghezza di attraversamento tradizionale usa una coda, non una pila. La natura di una coda e di uno stack sono praticamente opposti, quindi provare a usare lo stack di chiamate (che è una pila, da cui il nome) come lo storage ausiliario (una coda) è praticamente destinato a fallire, a meno che tu non stia qualcosa di stupidamente ridicolo con lo stack delle chiamate che non dovresti essere.

Allo stesso modo, la natura di qualsiasi ricorsione non a coda che si tenta di implementare è essenzialmente l'aggiunta di una pila all'algoritmo. In questo modo non viene più estesa la prima ricerca su un albero binario, e quindi il tempo di esecuzione e quant'altro per BFS tradizionale non si applicano più completamente. Naturalmente, puoi sempre banalmente trasformare qualsiasi loop in una chiamata ricorsiva, ma non è una sorta di ricorsione significativa.

Tuttavia, ci sono modi, come dimostrato da altri, per implementare qualcosa che segue la semantica di BFS ad un certo costo. Se il costo del confronto è costoso ma il nodo trasversale è economico, come ha fatto lo @Simon Buchan, puoi semplicemente eseguire una ricerca iterativa in profondità, elaborando solo le foglie. Ciò significherebbe che nessuna coda in crescita è archiviata nell'heap, solo una variabile di profondità locale e stack accumulati più e più volte nello stack di chiamate mentre l'albero viene attraversato più e più volte. E come notato da @Patrick, un albero binario supportato da un array viene in genere archiviato in ordine di attraversamento di ampiezza, quindi una ricerca in ampiezza su quella sarebbe banale, anche senza bisogno di una coda ausiliaria.

Answer 2

Non sono riuscito a trovare un modo per farlo completamente ricorsivo (senza alcuna struttura dati 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) 
} 

Answer 3

Se si utilizza una matrice per eseguire l'albero binario, si può determinare il nodo successivo algebricamente. se i è un nodo, i suoi figli possono essere trovati a 2i + 1 (per il nodo sinistro) e 2i + 2 (per il nodo destro). 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. Questo presuppone un array di dimensioni fisse e quindi un albero di profondità fissa. Guarderà i nodi senza genitori e potrebbe creare uno stack ingestibilmente 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

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

Answer 5

Ho dovuto implementare un attraversamento dell'heap che esce in un ordine BFS. In realtà non è BFS ma svolge lo stesso compito.

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

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 scopri la profondità dell'albero e fai questo per tutti i livelli, i risultati saranno gli stessi di 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); 

Trovare la profondità di un albero è un gioco da ragazzi.

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

Sia V vertice di partenza

Sia G il grafico in questione

Il seguente è 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) 

Answer 9

Ecco un pitone implementazione:

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

Ho trovato un algoritmo ricorsivo (persino funzionale) di ampiezza relativa al primo piano. Non è la mia idea, ma penso che dovrebbe essere menzionato in questo argomento.

Chris Okasaki spiega il suo ampio algoritmo di numerazione da ICFP 2000 allo 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 
} 

Answer 11

Ecco un'implementazione Scala 2.11.4 di ricorsiva BFS. Ho sacrificato l'ottimizzazione della coda per brevità, ma la versione TCOd è molto simile. Vedi anche il post di @snv.

Answer 12

Ecco una implementazione JavaScript che simula Larghezza Prima attraversamento con profondità Prima ricorsione. Sto memorizzando i valori del nodo ad ogni profondità all'interno di un array, all'interno di un hash. Se un livello esiste già (abbiamo una collisione), quindi dobbiamo solo passare alla matrice a quel livello. Potresti usare una matrice invece di un oggetto JavaScript poiché i nostri livelli sono numerici e possono servire come indici di array. È possibile restituire nodi, valori, convertire in un elenco collegato o qualsiasi altra cosa si desideri. Sto solo restituendo i 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 ] } */ 

Questo è un esempio di ampiezza del primo attraversamento iniziale 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 

Answer 13

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

Answer 14

Quanto segue mi sembra piuttosto naturale, 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]) 

Answer 15

seguito è il mio codice per tutto ricorsiva implementazione di breadth-first-cerca di una grafico bidirezionale senza utilizzare 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); 
     } 
    }