Primera búsqueda en profundidad en Java

Programación

1. Información general

En este tutorial, exploraremos la búsqueda en profundidad en Java.

La búsqueda en profundidad (DFS) es un algoritmo transversal que se utiliza para estructuras de datos de árbol y gráfico. La búsqueda en profundidad primero profundiza en cada rama antes de pasar a explorar otra rama .

En las siguientes secciones, primero veremos la implementación de un árbol y luego un gráfico.

Para ver cómo implementar estas estructuras en Java, eche un vistazo a nuestros tutoriales anteriores sobre Árbol binario y gráfico.

2. Búsqueda de la profundidad del árbol primero

Hay tres órdenes diferentes para atravesar un árbol usando DFS:

  1. Recorrido de pedidos anticipados
  2. Traversal en orden
  3. Traslado de pedidos posteriores

2.1. Recorrido de pedidos anticipados

En el recorrido de preorden, atravesamos primero la raíz, luego los subárboles izquierdo y derecho.

Simplemente podemos implementar el recorrido de preorden usando la recursividad :

  • Visita el nodo actual
  • Subárbol transversal izquierdo
  • Subárbol transversal derecho
public void traversePreOrder(Node node) { if (node != null) { visit(node.value); traversePreOrder(node.left); traversePreOrder(node.right); } }

También podemos implementar el recorrido de preorden sin recursividad.

Para implementar un recorrido iterativo de preorden, necesitaremos una pila y seguiremos estos pasos:

  • Empuje la raíz en nuestra tachuela
  • Mientras la pila no esté vacía
    • Pop actual nodo
    • Visita el nodo actual
    • Empuje al niño derecho , luego al niño izquierdo para apilar
public void traversePreOrderWithoutRecursion() { Stack stack = new Stack(); Node current = root; stack.push(root); while(!stack.isEmpty()) { current = stack.pop(); visit(current.value); if(current.right != null) { stack.push(current.right); } if(current.left != null) { stack.push(current.left); } } }

2.2. Traversal en orden

Para el recorrido en orden, atravesamos primero el subárbol izquierdo, luego la raíz y finalmente el subárbol derecho .

El recorrido en orden para un árbol de búsqueda binario significa atravesar los nodos en orden creciente de sus valores.

Simplemente podemos implementar el cruce en orden usando la recursividad:

public void traverseInOrder(Node node) { if (node != null) { traverseInOrder(node.left); visit(node.value); traverseInOrder(node.right); } }

También podemos implementar el recorrido en orden sin recursividad :

  • Empuje el nodo raíz hacia la tachuela
  • Mientras que la tachuela no está vacía
    • Siga empujando al niño izquierdo hacia la pila, hasta que lleguemos al niño más a la izquierda del nodo actual
    • Visita el nodo actual
    • Empuje al niño derecho sobre la pila
public void traverseInOrderWithoutRecursion() { Stack stack = new Stack(); Node current = root; stack.push(root); while(! stack.isEmpty()) { while(current.left != null) { current = current.left; stack.push(current); } current = stack.pop(); visit(current.value); if(current.right != null) { current = current.right; stack.push(current); } } }

2.3. Traslado de pedidos posteriores

Finalmente, en el recorrido postorder, atravesamos el subárbol izquierdo y derecho antes de atravesar la raíz .

Podemos seguir nuestra solución recursiva anterior :

public void traversePostOrder(Node node) { if (node != null) { traversePostOrder(node.left); traversePostOrder(node.right); visit(node.value); } }

O también podemos implementar el recorrido postorder sin recursividad :

  • Empuje el nodo raíz en la tachuela
  • Mientras que la tachuela no está vacía
    • Compruebe si ya hemos atravesado el subárbol izquierdo y derecho
    • Si no, empuje al niño derecho y al niño izquierdo hacia la pila
public void traversePostOrderWithoutRecursion() { Stack stack = new Stack(); Node prev = root; Node current = root; stack.push(root); while (!stack.isEmpty()) { current = stack.peek(); boolean hasChild = (current.left != null || current.right != null); boolean isPrevLastChild = (prev == current.right || (prev == current.left && current.right == null)); if (!hasChild || isPrevLastChild) { current = stack.pop(); visit(current.value); prev = current; } else { if (current.right != null) { stack.push(current.right); } if (current.left != null) { stack.push(current.left); } } } }

3. Búsqueda en profundidad del gráfico primero

La principal diferencia entre gráficos y árboles es que los gráficos pueden contener ciclos .

Entonces, para evitar buscar en ciclos, marcaremos cada nodo cuando lo visitemos.

Veremos dos implementaciones para el gráfico DFS, con recursividad y sin recursividad.

3.1. Graficar DFS con recursividad

Primero, comencemos de manera simple con la recursividad:

  • Empezaremos por un nodo dado
  • Marcar el nodo actual como visitado
  • Visita el nodo actual
  • Atravesar vértices adyacentes no visitados
public void dfs(int start) { boolean[] isVisited = new boolean[adjVertices.size()]; dfsRecursive(start, isVisited); } private void dfsRecursive(int current, boolean[] isVisited) { isVisited[current] = true; visit(current); for (int dest : adjVertices.get(current)) { if (!isVisited[dest]) dfsRecursive(dest, isVisited); } }

3.2. Graficar DFS sin recursividad

También podemos implementar el gráfico DFS sin recursividad. Simplemente usaremos una pila :

  • Empezaremos por un nodo dado
  • Empuje el nodo de inicio en la pila
  • Mientras la pila no está vacía
    • Marcar el nodo actual como visitado
    • Visita el nodo actual
    • Empuje vértices adyacentes no visitados
public void dfsWithoutRecursion(int start) { Stack stack = new Stack(); boolean[] isVisited = new boolean[adjVertices.size()]; stack.push(start); while (!stack.isEmpty()) { int current = stack.pop(); isVisited[current] = true; visit(current); for (int dest : adjVertices.get(current)) { if (!isVisited[dest]) stack.push(dest); } } }

3.4. Orden topológico

Hay muchas aplicaciones para la búsqueda en profundidad de gráficos. Una de las aplicaciones famosas de DFS es Topological Sort.

El ordenamiento topológico de un gráfico dirigido es un ordenamiento lineal de sus vértices de modo que para cada borde el nodo de origen se antepone al de destino.

Para ordenar topológicamente, necesitaremos una simple adición al DFS que acabamos de implementar:

  • Necesitamos mantener los vértices visitados en una pila porque el orden topológico son los vértices visitados en un orden inverso
  • Empujamos el nodo visitado a la pila solo después de atravesar todos sus vecinos
public List topologicalSort(int start) { LinkedList result = new LinkedList(); boolean[] isVisited = new boolean[adjVertices.size()]; topologicalSortRecursive(start, isVisited, result); return result; } private void topologicalSortRecursive(int current, boolean[] isVisited, LinkedList result) { isVisited[current] = true; for (int dest : adjVertices.get(current)) { if (!isVisited[dest]) topologicalSortRecursive(dest, isVisited, result); } result.addFirst(current); }

4. Conclusión

En este artículo, analizamos la búsqueda en profundidad para las estructuras de datos de árbol y gráfico.

El código fuente completo está disponible en GitHub.