Primera búsqueda en profundidad: una guía transversal de gráficos DFS con 6 ejemplos de códigos

¿Has resuelto alguna vez un laberinto de la vida real? El enfoque que la mayoría de nosotros tomamos al resolver un laberinto es seguir un camino hasta llegar a un callejón sin salida, y luego retroceder y volver sobre nuestros pasos para encontrar otro camino posible.

Esta es exactamente la analogía de la búsqueda en profundidad (DFS). Es un algoritmo de recorrido de gráfico popular que comienza en el nodo raíz y viaja lo más lejos que puede por una rama determinada, luego retrocede hasta encontrar otro camino inexplorado para explorar. Este enfoque se continúa hasta que se hayan visitado todos los nodos del gráfico.

En el tutorial de hoy, vamos a descubrir un patrón DFS que se utilizará para resolver algunas de las preguntas importantes sobre árboles y gráficos para su próxima entrevista de Tech Giant. Resolveremos algunos problemas de Leetcode Medio y Difícil utilizando la misma técnica común.

Entonces, comencemos, ¿de acuerdo?

Implementación

Dado que DFS tiene una naturaleza recursiva, se puede implementar mediante una pila.

Hechizo mágico DFS:

  1. Empuje un nodo a la pila
  2. Pop el nodo
  3. Recupere vecinos no visitados del nodo eliminado, empújelos para apilar
  4. Repita los pasos 1, 2 y 3 siempre que la pila no esté vacía

Gráficos recorridos

En general, hay 3 recorridos DFS básicos para árboles binarios:

  1. Pedido anticipado : raíz, izquierda, derecha o raíz, derecha, izquierda
  2. Orden de publicación: izquierda, derecha, raíz o derecha, izquierda, raíz
  3. En orden: izquierda, raíz, derecha o derecha, raíz, izquierda

144. Recorrido de reserva de árbol binario (dificultad: media)

Para resolver esta pregunta, todo lo que tenemos que hacer es simplemente recordar nuestro hechizo mágico. Entendamos muy bien la simulación ya que esta es la plantilla básica que usaremos para resolver el resto de problemas.

Al principio, empujamos el nodo raíz a la pila. Mientras la pila no está vacía, la sacamos y empujamos su hijo derecho e izquierdo hacia la pila.

A medida que sacamos el nodo raíz, lo colocamos inmediatamente en nuestra lista de resultados. Por tanto, el primer elemento de la lista de resultados es la raíz (de ahí el nombre Pre-order).

El siguiente elemento que se extraerá de la pila será el elemento superior de la pila en este momento: el hijo izquierdo del nodo raíz. El proceso continúa de manera similar hasta que se recorre todo el gráfico y todos los valores de los nodos del árbol binario entran en la lista resultante.

145. Cruce de posorden de árbol binario (dificultad: difícil)

El recorrido de preorden es root-left-right y el post-order es right-left-root . Esto significa que el recorrido posterior al pedido es exactamente lo contrario del recorrido posterior al pedido.

Entonces, una solución que podría venir a la mente en este momento es simplemente revertir la matriz resultante de recorrido de preorden. Pero piénselo, eso costaría O (n) tiempo de complejidad para revertirlo.

Una solución más inteligente es copiar y pegar el código exacto del recorrido de la reserva, pero poner el resultado en la parte superior de la lista vinculada (índice 0) en cada iteración. Se necesita un tiempo constante para agregar un elemento al encabezado de una lista vinculada. ¿Guay, verdad?

94. Desplazamiento por orden de árbol binario (dificultad: media)

Nuestro enfoque para resolver este problema es similar a los problemas anteriores. Pero aquí, visitaremos todo en el lado izquierdo de un nodo, imprimiremos el nodo y luego visitaremos todo en el lado derecho del nodo.

323. Número de componentes conectados en un gráfico no dirigido

(Dificultad: media)

Nuestro enfoque aquí es crear una variable llamada ans que almacena el número de componentes conectados.

Primero, inicializaremos todos los vértices como no visitados. Partiremos de un nodo, y mientras realizamos DFS en ese nodo (por supuesto, usando nuestro hechizo mágico), marcará todos los nodos conectados a él como visitados. El valor de ans se incrementará en 1.

 import java.util.ArrayList; import java.util.List; import java.util.Stack; public class NumberOfConnectedComponents { public static void main(String[] args){ int[][] edge = {{0,1}, {1,2},{3,4}}; int n = 5; System.out.println(connectedcount(n, edge)); } public static int connectedcount(int n, int[][] edges) { boolean[] visited = new boolean[n]; List[] adj = new List[n]; for(int i=0; i
    

200. Number of Islands (Difficulty: Medium)

This falls under a general category of problems where we have to find the number of connected components, but the details are a bit tweaked.

Instinctually, you might think that once we find a “1” we initiate a new component. We do a DFS from that cell in all 4 directions (up, down, right, left) and reach all 1’s connected to that cell. All these 1's connected to each other belong to the same group, and thus, our value of count is incremented by 1. We mark these cells of 1's as visited and move on to count other connected components.

547. Friend Circles (Difficulty: Medium)

This also follows the same concept as finding the number of connected components. In this question, we have an NxN matrix but only N friends in total. Edges are directly given via the cells so we have to traverse a row to get the neighbors for a specific "friend".

Notice that here, we use the same stack pattern as our previous problems.

That's all for today! I hope this has helped you understand DFS better and that you have enjoyed the tutorial. Please recommend this post if you think it may be useful for someone else!