Búsqueda inicial y profundidad Búsqueda inicial

Question

¿Alguien puede dar un enlace para una explicación simple sobre BFS y DFS con su implementación?

Answer 1

digamos que se le da la siguiente estructura:

 
Format: Node [Children] 

A [B C D] 
B [E F] 
C [G] 
D [] 
E [] 
F [] 
G [] 

Una búsqueda en anchura visitas todos los hijos de un nodo antes de visitar a sus hijos.Aquí está el pseudocódigo y la solución de 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 visitas al nivel más bajo (los niños más profundas) del árbol primera vez. 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 

Answer 2

recorrido del gráfico con dfs y bfs.

en c++ y python.

Answer 3

Éstos son algunos enlaces de revisar:

• Breadth-first search

BFS es un método de búsqueda desinformados que tiene como objetivo ampliar y examinar todos los nodos de un gráfico o una combinación de secuencias de búsqueda sistemática a través de 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.

• Depth-first search

Formalmente, DFS es una búsqueda desinformados que progresa mediante la ampliación del primer nodo hijo del árbol de búsqueda que aparece y por lo tanto va más y más hasta un nodo objetivo se encuentra , o hasta que llegue a un nodo que no tiene hijos. Entonces la búsqueda retrocede, volviendo a la más reciente nodo no ha terminado de explorar

No sólo contienen buenas explicaciones sobre la forma en que se implementan en las aplicaciones, sino también un cierto código de pseudo algoritmo.

Answer 4

Digamos que tiene un árbol de la siguiente manera:

alt text http://i40.tinypic.com/289aslh.jpg

Puede ser un poco confuso porque E es a la vez un niño de A y F, pero que 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. Por lo tanto, el recorrido de izquierda a derecha sería A, B, D, F, E, C, G.

Una primera búsqueda de amplitud evalúa primero a todos los niños antes de proceder con los hijos de los niños. Así mismo árbol iría A, B, C, E, D, F, G.

Espero que esto ayude.

Answer 5

Breadth First Search/Depth First Search Animations

Answer 6

se puede encontrar todo en el wiki:

BFS y DFS

este link puede ser útil también. si quieres una aplicación vaya a: c++ boost library: DFS

Answer 7

primera búsqueda en profundidad:

Answer 8

Heres la idea en lo básico:

obtener una nueva cola ... inicializar con el nodo raíz .. .. recorra toda la cola y continúe eliminando un elemento de la cola e imprimiéndolo (o guardándolo, etc.) y verifique si el mismo elemento tiene alguna niños, si es así, empújelos a la cola y continúe en el ciclo hasta que recorra todo el segmento (gráfico) ...

Answer 9

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

Answer 10

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. DFS visitas profundidad de cada rama primero. 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.

Answer 11

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 -,,.

Preorder:

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). 

Nivel de orden transversal Tiempo Complejidad O (n) - Número de veces que se visitó cada nodo es 1 solamente, significa total es n veces.

espacio complejidad- Mejor caso: Árbol solamente los nodos de la izquierda, es O (1) Caso media: árbol binario perfecto es ejemplo, n/2 número de nodos, O (n)