Exécution Première recherche récursive Largeur
https://stackoverflow.com/questions/2549541
-
23-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Disons que vous vouliez mettre en œuvre une recherche en largeur d'un arbre binaire récursive . Comment feriez-vous à ce sujet?
Est-il possible en utilisant uniquement l'appel pile comme mémoire auxiliaire?
La solution
(je suppose que cela est juste une sorte de pensée exercice, ou même un devoir trick / question d'entrevue, mais je suppose que je pourrais imaginer un scénario bizarre où vous n'êtes pas autorisé un espace de tas pour une raison quelconque [certains vraiment mauvais gestionnaire de mémoire personnalisé? certains problèmes d'exécution / OS bizarre?] pendant que vous avez toujours accès à la pile ...)
parcours en largeur utilise traditionnellement une file d'attente, et non pas une pile. La nature d'une file d'attente et une pile sont à peu près en face, si vous essayez d'utiliser la pile d'appel (ce qui est une pile, d'où le nom) que le stockage auxiliaire (une file d'attente) est à peu près vouée à l'échec, à moins que vous faites quelque chose bêtement ridicule avec la pile d'appel que vous ne devriez pas être.
Dans le même ordre d'idées, la nature de toute récursivité non-queue que vous essayez de mettre en œuvre est essentiellement l'ajout d'une pile à l'algorithme. Cela le rend pas plus étendue première recherche sur un arbre binaire, et donc l'exécution et ainsi de suite pour BFS traditionnelle ne s'appliquent plus complètement. Bien sûr, vous pouvez toujours tourner trivialement une boucle dans un appel récursif, mais ce n'est pas une sorte de récursion significative.
Cependant, il existe des moyens, comme en témoigne par d'autres, pour mettre en œuvre quelque chose qui suit la sémantique de BFS à un coût. Si le coût de comparaison est cher, mais le noeud traversal est pas cher, puis comme @Simon Buchan fait, vous pouvez simplement lancer une recherche en profondeur d'abord itérative, le traitement que les feuilles. Cela signifierait aucune file d'attente de plus en plus stocké dans le tas, à une profondeur variable locale, et des piles en cours de construction au-dessus et plus sur la pile d'appel que l'arbre est traversé maintes et maintes fois. Et comme @Patrick a noté, un arbre binaire soutenu par un tableau est généralement stockées dans largeur d'abord traversal de toute façon, donc une largeur d'abord la recherche sur ce serait trivial, aussi sans avoir besoin d'une file d'attente auxiliaire.
Autres conseils
Si vous utilisez un tableau pour sauvegarder l'arbre binaire, vous pouvez déterminer le nœud suivant algébriquement. si i est un nœud, puis ses enfants se trouvent à 2i + 1 (pour le nœud de gauche) et 2i + 2 (pour le nœud à droite). est donnée voisin d'un nœud par i + 1, à moins i est une puissance de 2
Voici une mise en œuvre pseudocode très naïve de la recherche sur la largeur d'abord un tableau soutenu par arbre de recherche binaire. Cela suppose une matrice de taille fixe et par conséquent, un arbre de profondeur fixe. Il se penchera sur les noeuds-enfants, et pourrait créer une pile ingérable.
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)
Je ne pouvais pas trouver un moyen de le faire complètement récursive (sans auxiliaire structure de données). Mais si la file d'attente Q est passé par référence, alors vous pouvez avoir la fonction récursive de la queue stupide suivante:
BFS(Q)
{
if (|Q| > 0)
v <- Dequeue(Q)
Traverse(v)
foreach w in children(v)
Enqueue(Q, w)
BFS(Q)
}
La méthode suivante utilise un algorithme DFS pour obtenir tous les noeuds dans une profondeur particulière - qui est le même que faire BFS pour ce niveau. Si vous trouvez la profondeur de l'arbre et le faire pour tous les niveaux, les résultats seront identiques à 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);
}
profondeur Conclusion d'un arbre est un morceau de gâteau:
public int MaxDepth(Tree root) {
if (root == null) {
return 0;
} else {
return Math.Max(MaxDepth(root.Left), MaxDepth(root.Right)) + 1;
}
}
Un BFS simple et récursion DFS en Java:
Il suffit de pousser / offrent le nœud racine de l'arbre dans la pile / file d'attente et appeler ces fonctions.
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);
}
La façon stupide:
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;
}
J'ai trouvé une très belle récursif (même fonctionnelle) en largeur algorithme lié traversal. Pas mon idée, mais je pense qu'il convient de mentionner dans ce sujet.
Chris Okasaki explique son algorithme en largeur au nombre de ICFP 2000 à http://okasaki.blogspot.de/2008/07/breadth-first-numbering-algorithm-in.html très clairement avec seulement 3 images.
La mise en œuvre de Scala Debasish Ghosh, que j'ai trouvé à http : //debasishg.blogspot.de/2008/09/breadth-first-numbering-okasakis.html, est:
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
}
Voici une implémentation 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)
Voici une Scala 2.11.4 mise en œuvre de BFS récursive. J'ai sacrifié l'optimisation appel de la queue par souci de concision, mais la version ODMTC est très similaire. Voir aussi @snv poste de .
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]
}
Ce qui suit me semble assez naturel, en utilisant Haskell. Itérer récursive par rapport aux niveaux de l'arbre (ici, je collectionne les noms dans une grande chaîne de l'ordre de montrer le chemin à travers l'arbre):
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])
Voici court Scala Solution:
def bfs(nodes: List[Node]): List[Node] = {
if (nodes.nonEmpty) {
nodes ++ bfs(nodes.flatMap(_.children))
} else {
List.empty
}
}
Idée de en utilisant la valeur de retour comme accumulateur est bien adapté. Peut être mis en œuvre dans d'autres langues dans la même manière, assurez-vous que votre processus de fonction récursive liste des nœuds .
Code d'essai liste (en utilisant @marco arbre 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())))
}
}
Sortie:
List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
Je devais mettre en œuvre un traversal tas qui sort dans un ordre BFS. Elle ne fait pas BFS mais accomplit la même tâche.
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;
}
Soit v le sommet de départ
Soit G le graphe en question
Ce qui suit est le pseudo-code sans utiliser de file d'attente
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 pour un arbre binaire (ou n-aire) peut se faire sans files d'attente récursive comme suit (ici 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 exemple des numéros d'impression de parcours 1-12 dans l'ordre croissant:
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;
}
Voici une implémentation JavaScript qui truque Traversal avec largeur d 'abord en profondeur d'abord récursivité. Je mémoriser les valeurs de nœud à chaque profondeur à l'intérieur d'un tableau, à l'intérieur d'une table de hachage. Si un niveau existe déjà (nous avons une collision), donc nous poussons juste au tableau à ce niveau. Vous pouvez utiliser un tableau au lieu d'un objet JavaScript et puisque nos niveaux sont numériques et peuvent servir d'indices de tableau. Vous pouvez retourner les nœuds, les valeurs, se convertir à une liste chaînée, ou tout ce que vous voulez. Je suis juste le retour des valeurs par souci de simplicité.
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 ] } */
Voici un exemple de réelle largeur d'abord Traversal en utilisant une approche itérative.
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
Après mon code pour la mise en œuvre complètement récursive de largeur-première recherche d'un graphique bi-directionnel sans utiliser la boucle et la file d'attente.
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);
}
}
Voici une implémentation Python traversal récursive BFS, travaillant pour un graphe sans cycle.
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 = []
