algorithm - una - Ampliar la primera búsqueda y profundidad Primera búsqueda
meta name description content (11)
¿Alguien puede dar un enlace para una explicación simple sobre BFS y DFS con su implementación?
Aquí está la idea en lo básico:
obtener una nueva cola ... initalizarla con el nodo raíz ... recorrer toda la cola y seguir eliminando un elemento de la cola e imprimirlo (o guardarlo, etc.) y comprobar si el mismo elemento tiene hijos, si es así, empújelos a la cola y continúe en el ciclo hasta que recorra todo el segmento (gráfico) ...
Aquí hay algunos enlaces para ver:
BFS es un método de búsqueda desinformado que tiene como objetivo expandir y examinar todos los nodos de un gráfico o combinación de secuencias al buscar sistemáticamente en cada solución. En otras palabras, busca de manera exhaustiva todo el gráfico o la secuencia sin considerar el objetivo hasta que lo encuentra.
Formalmente, DFS es una búsqueda desinformada que progresa expandiendo el primer nodo secundario del árbol de búsqueda que aparece y, por lo tanto, profundizando cada vez más hasta que se encuentra un nodo objetivo o hasta que llega a un nodo que no tiene hijos. Luego la búsqueda retrocede, volviendo al nodo más reciente, no ha terminado de explorar
No solo contienen buenas explicaciones sobre cómo se implementan en las aplicaciones, sino también algún pseudo código de algoritmo.
BFS y DFS son aplicables a todo tipo de gráficos. Lo explico solo para árbol binario. BFS visita cada nodo de arriba a abajo, de izquierda a derecha. Por ejemplo para esto:
1
/ /
7 9
/ / /
8 2 3
BFS nos da: 1 7 9 8 2 3. Primero, DFS visita la profundidad de cada rama. Luego, regresa a sus padres. Puedes seguir esta regla informal. Primero dejó al niño, luego a la derecha, luego al padre. Pero, debes comenzar desde la profundidad de cada rama. Por ejemplo, aquí comienza desde 8, ya que no hay ningún niño de la izquierda por 7. Luego, visita al padre 7. Luego, se visitará a uno de los padres de 7. Entonces, vas a la rama derecha. Pero, esta vez hay 2 como el niño más a la izquierda. Entonces, visita 2 (hijo izquierdo), luego hijo derecho 3, luego 9 sus padres. Entonces, DFS nos da 8 7 1 2 9 3. Esta es la implementación:
import java.util.ArrayList;
import java.util.List;
public class TreeTraverse {
static class Node{
Node(int data){
this.data = data;
this.left = null;
this.right = null;
this.visited = false;
}
int data;
Node left;
Node right;
boolean visited;
}
public static void main(String[] args) {
//The tree:
// 1
// / /
// 7 9
// / / /
// 8 2 3
Node node1 = new Node(1);
Node node7 = new Node(7);
Node node9 = new Node(9);
Node node8 = new Node(8);
Node node2 = new Node(2);
Node node3 = new Node(3);
node1.left = node7;
node1.right = node9;
node7.right = node8;
node9.right = node3;
node9.left = node2;
System.out.println("DFS: ");
depthFirstSearch(node1);
System.out.println("/nBFS: ");
breadthFirstSearch(node1);
}
private static void depthFirstSearch(Node node){
if(node.left == null && node.right == null){
System.out.print(node.data+" ");
node.visited = true;
}else if(node.left == null || node.left.visited){
depthFirstSearch(node.right);
System.out.print(node.data+" ");
node.visited = true;
}else{
depthFirstSearch(node.left);
node.visited = true;
System.out.print(node.data+" ");
depthFirstSearch(node.right);
}
}
private static void breadthFirstSearch(Node node){
List<Node> al = new ArrayList<>();
al.add(node);
while(!al.isEmpty()){
node = al.get(0);
if(node.left != null){
int index = al.size();
al.add(index,node.left);
}
if(node.right != null){
int index = al.size();
al.add(index,node.right);
}
System.out.print(al.get(0).data+" ");
al.remove(0);
}
}
}
Espero que ayude. Si desea clonar el proyecto, visite: https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java . Espero que ayude.
Digamos que te dan la siguiente estructura:
Format: Node [Children] A [B C D] B [E F] C [G] D [] E [] F [] G []
Una primera búsqueda de amplitud visita todos los hijos de un nodo antes de visitar a sus hijos. Aquí está el pseudocódigo y la solución para la estructura anterior:
1. Enqueue root node. 2. Dequeue and output. If the queue is empty, go to step 5. 3. Enqueue the dequeued node''s children. 4. Go to Step 2. 5. Done
Two queues: (Active Node) [Output] [Working Set] Starting with root: ( ) [] [A] (A) [A] [B C D] (B) [A B] [C D E F] (C) [A B C] [D E F G] (D) [A B C D] [E F G] (E) [A B C D E] [F G] (F) [A B C D E F] [G] (G) [A B C D E F G] [] Done
Una primera búsqueda en profundidad visita primero el nivel más bajo (los niños más profundos) del árbol. Hay dos tipos de búsqueda en profundidad: preordenar y postordenar. Esto solo diferencia entre cuando agrega el nodo a la salida (cuando lo visita y lo deja).
var rootNode = structure.getRoot(); var preOrder = new Array(); var postOrder = new Array(); function DepthFirst( rootNode ){ // Pre-order preOrder[ preOrder.length ] = rootNode; for( var child in rootNode ){ DepthFirst( child ); } // Post-order postOrder[ postOrder.length ] = rootNode; }
Pre-order: * A B E F C G D Post-order: * E F B G C D A
Digamos que tienes un árbol de la siguiente manera:
texto alternativo http://i40.tinypic.com/289aslh.jpg
Puede ser un poco confuso porque E es un niño de A y F, pero ayuda a ilustrar la profundidad en una primera búsqueda en profundidad. Una primera búsqueda en profundidad busca el árbol que va tan profundo (de ahí el término profundidad) como puede hacerlo primero. Entonces, el recorrido de izquierda a derecha sería A, B, D, F, E, C, G.
Una primera búsqueda de amplitud evalúa a todos los niños primero antes de proceder a los hijos de los niños. Así que el mismo árbol iría A, B, C, E, D, F, G.
Espero que esto ayude.
En primer lugar, BFS y DFS son dos formas de implementar el cruce de árbol binario. Breadth First significa cruce de orden de nivel. Profundidad Primero tiene tres formas de implementar -,,.
Hacer un pedido:
a. Start with root,
b. mark it visited,
c. go to left node
d. (b) - mark it visited
e. Repeat (c) till there is not any new left node remaining
(We are/might be at leaf node at this point,)
f. Is there any right node available? If yes, go to (a).
Complejidad de tiempo transversal de orden de nivel O (n): el número de veces que se visita cada nodo es 1 solamente, significa que el total es n veces.
Complejidad espacial: mejor caso: árbol solo nodos a la izquierda, es O (1) Caso promedio: árbol binario perfecto es ejemplo, n / 2 número de nodos, O (n)
fragmento con 2 punteros.
void BFS(int v,struct Node **p)
{
struct Node *u;
visited[v-1] = TRUE;
printf("%d/t",v);
AddQueue(v);
while(IsEmpty() == FALSE)
{
v = DeleteQueue();
u = *(p+v-1);
while(u!=NULL)
{
if(visited(u->data -1) == FALSE)
{
AddQueue(u->data);
visited[u->data -1]=TRUE;
printf("%d/t",u->data);
}
u = u->next;
}
}
}
puedes encontrar todo en wiki:
este link puede ser útil. si quieres una implementación ve a: biblioteca de refuerzo de C ++: DFS
Profundidad Primera búsqueda: