Introducción
Contenido
Las preguntas de entrevistas relacionadas con gráficos son muy comunes, y se espera que conozca muchos algoritmos que entran en esta categoría.
Es importante familiarizarse con todos estos algoritmos: la motivación detrás de ellos, sus implementaciones y aplicaciones.
Si está interesado en leer más sobre Programación de preguntas de entrevista en general, hemos compilado una lista extensa de estas preguntas, incluidas sus explicaciones, implementaciones, representaciones visuales y aplicaciones.
Preguntas de la entrevista sobre la estructura de datos del gráfico
Dicho claramente: un gráfico es una estructura de datos no lineal formada por nodes / vértices y bordes.
Los nodes son entidades en nuestro gráfico y los bordes son las líneas que los conectan:
Representación de una gráfica
Hay muchos tipos de gráficos, gráficos no dirigidos, gráficos dirigidos, gráficos con etiquetas de vértice, gráficos cíclicos, gráficos con etiquetas de bordes, gráficos ponderados, etc.
No obstante, se utilizan con mayor frecuencia para representar redes, ya sea una red de ciudad, calles de la ciudad, un terreno para que pase la IA o conexiones de redes sociales.
Amplitud primera búsqueda
Ejemplo de pregunta de entrevista
Encuentra el camino más corto en un laberinto. Los bloques de ruta se representan como 1y los bloques de pared se representan como 0. Puede moverse en cuatro direcciones (arriba, abajo, izquierda, derecha).
0, 0, 0, 0, 0, 0, 0, 1, 1
0, 1, 1, 1, 1, 0, 0, 1, 0
0, 1, 0, 0, 1, 1, 1, 1, 0
1, 1, 1, 0, 1, 0, 0, 0, 0
1, 0, 1, 1, 1, 1, 1, 1, 1
1, 1, 0, 0, 0, 0, 0, 0, 0
0, 1, 0, 0, 1, 1, 1, 1, 0
0, 1, 0, 0, 1, 0, 0, 1, 0
0, 1, 1, 1, 1, 0, 0, 1, 1
Explicación
Breadth First Search (BFS para abreviar) es un algoritmo de recorrido de gráficos, a menudo utilizado para encontrar la ruta más corta desde el node inicial hasta el node objetivo.
BFS visita «capa por capa». Esto significa que en un gráfico como el que se muestra a continuación, primero visita a todos los hijos del node inicial. Estos niños son tratados como la «segunda capa».
Después de visitar a todos los hijos del node inicial, el algoritmo visita a todos los hijos de los hijos ya visitados, prácticamente moviéndose a la tercera capa.
Te puede interesar:Leer un archivo línea por línea en Node.jsEs importante tener en cuenta que BFS llegará al final del gráfico y luego calculará la ruta más corta posible. Garantiza encontrar la ruta más corta posible, aunque paga el precio de no ser tan amigable con la memoria como otros algoritmos.
Para lograr esto, BFS usa a Queuey esta es una característica importante del algoritmo. La condición terminal del algoritmo es que Queueestá vacío, por lo que continuará hasta que visite todos los nodes.
Echemos un vistazo al pseudocódigo detrás de la implementación:
Queue queue
node set visited true
queue.enqueue(node)
while queue not empty
current = queue.dequeue()
for v in current children
if v is not visited
v set visited true
queue.enqueue(v)
Comenzamos agregando el node inicial a la cola. Dado que la cola no está vacía, configuramos el node actual para que sea el node raíz y lo eliminamos de la cola.
Luego, verificamos a todos los hijos del node actual y los visitamos si no los hemos visitado antes. Después de eso, agregamos a los niños a la cola.
Cada uno de estos niños se convertirá en el próximo currentnode. Y dado que la estructura de datos de la cola sigue la estructura FIFO (Primero en entrar , primero en salir), visitamos al resto de los niños de la segunda capa, antes de continuar visitando a los niños de las capas anteriores.
Aplicaciones BFS
«¿Dónde podemos usar BFS?»
¡Este algoritmo se utiliza en muchos sistemas a tu alrededor! Se usa muy a menudo para la búsqueda de rutas, junto con la búsqueda en profundidad. Se utiliza en su sistema de navegación GPS para encontrar ubicaciones vecinas e incluso en sitios web de redes sociales y motores de búsqueda.
BFS se usó mucho en inteligencia artificial y Machine Learning, especialmente en robótica. Y probablemente lo más notable, en su carrera de programación, se está utilizando para la recolección de basura.
Primera búsqueda en profundidad
Ejemplo de pregunta de entrevista
Compruebe si el gráfico dado está fuertemente conectado o no:
Explicación
La búsqueda primero en profundidad (DFS) es otro algoritmo de recorrido de gráficos, similar a la búsqueda primero en profundidad.
DFS busca lo más lejos posible a lo largo de una rama y luego retrocede para buscar lo más lejos posible en la siguiente rama. Esto significa que en el gráfico anterior, comienza con el primer vecino y continúa por la línea lo más lejos posible.
Te puede interesar:Teoría de la computación: máquinas de estados finitosUna vez que llega al node final en esa rama (1), retrocede al primer node donde se enfrentó con la posibilidad de cambiar de rumbo (5) y visita toda esa rama, en nuestro caso solo (2).
Luego retrocede nuevamente al node (5) y dado que ya ha visitado los nodes (1) y (2), retrocede a (3) y se redirecciona a la siguiente rama (8).
El algoritmo continúa atravesando de esta manera hasta que se han visitado todos los nodes y la pila está vacía.
DFS no garantiza encontrar la ruta más corta posible y puede conformarse con un óptimo local, a diferencia de BFS. Gracias a esto, es más amigable con la memoria, aunque no mucho.
Para lograr esto, DFS usa a Stack, que es la principal diferencia entre estos dos algoritmos. A Stacksigue una estructura LIFO (último en entrar, primero en salir), que es la razón por la que llega lo más lejos posible, antes de tomar en consideración las otras capas.
Puede implementar DFS con la ayuda de recursividad o iteración. El enfoque recursivo es más corto y simple, aunque ambos enfoques son prácticamente iguales en cuanto al rendimiento.
Echemos un vistazo al pseudocódigo recursivo detrás de la implementación:
dfs(node)
node set visited true
for n in node neighbors
if n is not visited
dfs(n)
Comenzamos llamando al algoritmo en el node dado y configuramos que es visitado.
Luego, verificamos todos los vecinos del node y, para cada uno, ejecutamos el mismo algoritmo si no se visita. Esto significa que antes de avanzar al siguiente vecino, visita a todos los hijos del primer vecino. Luego regresa a la cima y visita al segundo vecino, que avanza en la búsqueda de todos sus hijos, y así sucesivamente.
Es posible que haya notado la falta de Stacken este ejemplo y me gustaría abordarlo correctamente. Ambos enfoques usan una Stackestructura en segundo plano, aunque en el enfoque recursivo, no lo definimos explícitamente como tal.
Echemos un vistazo al pseudocódigo iterativo detrás de la implementación:
dfs(node)
Stack stack
node set visited true
stack.push(node)
while stack is not empty
current = stack.pop()
for n in node neighbors
if n is not visited
n set visited true
stack.push(n)
Aquí, agregamos el node inicial al Stack. Dado que la pila no está vacía, configuramos el currentnode para que sea el node inicial y lo sacamos de la pila.
Consideramos a todos los vecinos, uno por uno. El primer vecino se agrega a la pila, lo que lo convierte en el nuevo currentnode en la siguiente iteración. De esta forma, todos los hijos de este node se comprobarán antes que el node junto a este, de la lista de vecinos original.
Aplicaciones DFS
«¿Dónde podemos usar DFS?»
Similar a BFS, DFS se usa a menudo en inteligencia artificial y Machine Learning. Estos dos algoritmos son muy comunes y, a menudo, se comparan.
DFS se usa generalmente para buscar caminos entre nodes, y especialmente para encontrar caminos para laberintos. DFS también se utiliza para ordenar topológicamente y encontrar componentes fuertemente conectados.
Una búsqueda
Dado el siguiente gráfico, donde el node negro es el node inicial, los nodes rojos son las paredes y el node verde es el node objetivo, encuentre el camino más corto al node verde:
Explicación
Una * búsqueda es bastante diferente a las dos de las que hemos hablado anteriormente. También es un algoritmo de recorrido de gráficos, sin embargo, se usa para manejar escenarios de búsqueda de rutas de la vida real.
Una búsqueda * se basa en un conocimiento y una función de costo heurístico para el node dado como una forma de decidir qué node debe visitar a continuación. En la mayoría de los casos, esta función de costo se denota como f(x).
La función de costo se calcula como la suma de otras dos funciones:
g(x)– La función que representa el costo de pasar del node inicial a un node dado.h(x)– El costo estimado desde el node dado hasta el node objetivo.
Obviamente, no conocemos el costo de movimiento exacto desde la nota dada hasta el node objetivo, que es la razón por la h(x)que a menudo también se la denomina «heurística».
El algoritmo siempre elige el node con el valor más f(x)bajo . Esto es lógico, considerando cómo se calcula la función.
Cuantos menos pasos demos desde el punto de partida, combinados con lo cerca que nos acerquemos a la meta, el valor será f(x)más bajo si vamos por el camino más corto hacia la meta. Alejarse de la meta y dar más pasos de los necesarios para alcanzarla aumenta la f(x)función.
Aplicaciones de búsqueda A *
«¿Dónde podemos utilizar A * Search?
Te puede interesar:4 increíbles aplicaciones de Android para descargar vídeos de YouTubeEste algoritmo se usa generalmente para la mayoría de los problemas de ruta más corta. A menudo se usa para escenarios de búsqueda de la vida real, así como para videojuegos. La mayoría de los NPC y los jugadores de IA confían en A * para buscar un camino de forma inteligente, rápida y eficiente.
Algoritmo de Dijkstra
Dado el siguiente gráfico ponderado, encuentre el camino más corto entre los vértices A y H.
Explicación
El algoritmo Dijkstra es un notorio algoritmo de recorrido de grafos para encontrar la ruta más corta desde un node / vértice dado a otro.
Hay varias implementaciones de este algoritmo y algunas incluso usan diferentes estructuras de datos y tienen diferentes aplicaciones. Cubriremos el clásico: encontrar el camino más corto entre dos nodes.
Dijkstra funciona de una manera ligeramente diferente a los algoritmos anteriores. En lugar de comenzar en el node raíz, comienza en el node objetivo y retrocede hasta el node inicial.
El algoritmo hace esto construyendo un conjunto de notas con la distancia mínima desde la fuente, dictada por el «peso» de los bordes.
Está construido con algunas variables:
- dist : la distancia desde el node de destino (a menudo denominado node de origen) a todos los demás nodes del gráfico. El
distal node de origen es 0 ya que ahí es donde comenzamos. Además, la distancia a todos los demás nodes se establece en infinito. A medida que el algoritmo atraviesa el gráfico, la distancia a todos los demás nodes se vuelve a calcular de acuerdo con el node actual. - P – Similar a BFS, necesitamos definir un tipo de datos de Cola y llenarlo con todos los nodes del gráfico. La condición terminal para el algoritmo es si la cola está vacía.
- Conjunto : también necesitaremos un conjunto que contenga todos los nodes visitados, para no volver a visitarlos. Al final, el conjunto contendrá todos los nodes del gráfico.
Echemos un vistazo al pseudocódigo detrás de su implementación:
dijkstra(Graph, source)
source set distance 0
for n in Graph
if n is not source
n set dist infinity
n set parent none
queue.add(n)
while Q is not empty
n = node in Q with min dist(n)
remove n from Q
for node in n neighbors
i = dist(n) + length(node, goal)
if i < dist(goal)
dist(goal) = i
Aplicaciones de Dijkstra
«¿Dónde podemos usar Dijkstra?»
Este algoritmo se usa generalmente para muchos de los problemas de ruta más corta, y definitivamente es un algoritmo notable.
Google Maps utiliza Dijkstra para encontrar el camino más corto en la navegación. El enrutamiento IP también depende en gran medida exactamente de Dijkstra y tiene aplicaciones en redes de computadoras.
Comparando BFS, DFS, A * y Dijkstra
Puede que esto no surja como una pregunta de entrevista, pero sin duda es una pregunta lógica. Hemos cubierto 4 algoritmos diferentes que se utilizan principalmente para el mismo propósito.
Te puede interesar:¿Cómo aprender a programar?«¿Cuál debo usar? ¿Cuál es el mejor?»
La respuesta a esta pregunta común es: todos .
Cada uno de estos algoritmos, aunque aparentemente similar, ofrece ventajas sobre el otro, según la situación en la que los esté implementando y su caso específico.
A continuación, se muestran algunos casos en los que podría elegir cuál usaría:
- Encontrar miembros actualmente vivos en un árbol genealógico.
En tal caso, sería mejor usar DFS ya que la mayoría de los niveles más lejanos están vivos. BFS perdería demasiado tiempo considerando niveles que no deberían tenerse en cuenta. No tendría sentido usar Dijkstra o A * para este propósito.
- Encontrar a los miembros fallecidos en un árbol genealógico.
En tal caso, usar DFS sería menos práctico que BFS ya que la mayoría de los miembros fallecidos se ubicarían cerca de la parte superior. BFS atravesaría este gráfico capa por capa y agregaría todos los miembros relevantes a la lista.
- Encontrar el camino más corto del punto A al punto B en un gráfico / mapa.
En tal caso, aunque un poco controvertido, usar la búsqueda A * sobre Dijkstra es una práctica común. Usar BFS y DFS aquí puede ser muy poco práctico. BFS asume que el peso entre todos los nodes es el mismo, mientras que el peso / costo real podría variar. ¡Aquí es donde entra en juego Dijkstra!
Dijkstra tiene en cuenta el costo de moverse en un extremo. Si el costo de seguir recto es mayor que dar la vuelta, se distribuirá. Esto puede traducirse en carreteras congestionadas en un mapa por ejemplo.
A * se enfoca en alcanzar la meta, y solo da pasos que parecen prometedores y razonables, de acuerdo con sus funciones.
Dijkstra toma en consideración todos los demás nodes, mientras que A * solo toma los razonables. Debido a esto, A * es más rápido que Dijkstra y a menudo se considera «el algoritmo de búsqueda inteligente».
Algunos también se refieren a A * como el algoritmo de Dijkstra «informado». Si elimina la heurística de A *, lo que significa que elige el siguiente paso solo de acuerdo con el costo hasta ahora, prácticamente obtiene Dijkstra, aunque al revés. Esto hace que A * corra no con avidez hacia la meta, sino en todas las direcciones considerando cada node en el gráfico, que nuevamente es lo mismo que Dijkstra.
Si está buscando una búsqueda optimizada y resultados que se fijen exclusivamente en el objetivo, A * es la opción para usted.
Te puede interesar:Ejemplo: Apache Camel y BlueprintSi está buscando un algoritmo para calcular la ruta más corta entre el punto de partida y cada uno de los nodes del árbol, que incluye el node objetivo, Dijkstra es la opción para usted.
Recursos
Si está buscando una mejor manera de practicar este tipo de preguntas de entrevistas de programación, así como otras, le recomendamos que pruebe un servicio como Daily Coding Problem . Te enviarán un nuevo problema para resolver todos los días, todos los cuales provienen de las mejores empresas. También puede obtener más información aquí si desea más información.
Conclusión
En este artículo, hemos cubierto las preguntas comunes de las entrevistas relacionadas con la estructura de datos del gráfico.
Nuevamente, si está interesado en leer más sobre Programación de preguntas de entrevista en general, hemos compilado una lista extensa de estas preguntas, incluidas sus explicaciones, implementaciones, representaciones visuales y aplicaciones.
