Gráfico Estructura de datos Preguntas de la entrevista

Las preguntas de entrevistas relacionadas con gráficos son muy comunes, y muchos algoritmos que se espera que conozcas entran en esta categoría. Es importante conocer...

Introducción

Las preguntas de entrevistas relacionadas con gráficos son muy comunes, y muchos algoritmos que se espera que conozcas entran en esta categoría.

Es importante estar familiarizado con todos estos algoritmos: la motivación detrás de ellos, sus implementaciones y aplicaciones.

Si estás interesado en leer más sobre Preguntas de la entrevista de programación en general, hemos compilado una larga lista de estas preguntas, incluyendo su 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 compuesta de nodos/vértices y bordes.

Los nodos son entidades en nuestro gráfico, y los bordes son las líneas que los conectan:

what_are_graphs

[Representación de un gráfico]{.small}

Hay muchos tipos de gráficos, gráficos no dirigidos, gráficos dirigidos, gráficos con etiquetas de vértices, gráficos cíclicos, gráficos con etiquetas de borde, gráficos ponderados, etc.

No obstante, se utilizan con mayor frecuencia para representar redes, ya sea una red de ciudades, calles de ciudades, un terreno para que pase la IA o conexiones de redes sociales.

Búsqueda primero en amplitud

Ejemplo de pregunta de entrevista

Encuentra el camino más corto en un laberinto. Los bloques de ruta se representan como 1 y los bloques de pared se representan como 0. Puede moverse en cuatro direcciones (arriba, abajo, izquierda, derecha).

1
2
3
4
5
6
7
8
9
                 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 gráfico transversal, a menudo utilizado para encontrar la ruta más corta desde el nodo de inicio hasta el nodo de destino.

BFS visita "capa por capa". Esto significa que en un gráfico como el que se muestra a continuación, primero visita todos los elementos secundarios del nodo inicial. Estos niños son tratados como la "segunda capa".

bfs_search_gif

Después de visitar todos los hijos del nodo inicial, el algoritmo visita todos los hijos de los hijos ya visitados, prácticamente moviéndose a la tercera capa.

Es importante tener en cuenta que BFS llegará al final del gráfico y luego calculará la ruta más corta posible. Garantiza encontrar el camino más corto posible, aunque paga el precio de no ser tan compatible con la memoria como otros algoritmos.

Para lograr esto, BFS usa una Cola y esta es una característica importante del algoritmo. La condición terminal del algoritmo es que la ‘Cola’ está vacía, por lo que continuará hasta que visite todos los nodos.

Echemos un vistazo al pseudocódigo detrás de la implementación:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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 nodo inicial a la cola. Dado que la cola no está vacía, configuramos el nodo actual para que sea el nodo raíz y lo eliminamos de la cola.

Luego verificamos todos los hijos del nodo actual y los visitamos si no los hemos visitado antes. Después de eso, agregamos los niños a la cola.

Cada uno de estos hijos se convertirá en el siguiente nodo actual. Y dado que la estructura de datos de la cola sigue la estructura FIFO (Primero en entrar, primero en salir), visitamos el resto de los elementos secundarios de la segunda capa, antes de continuar visitando a los elementos secundarios de las capas anteriores.

Aplicaciones BFS

"¿Dónde podemos usar BFS?"

¡Este algoritmo se usa en muchos sistemas a tu alrededor! Se utiliza muy a menudo para la búsqueda de rutas, junto con la búsqueda de primera profundidad. Se está utilizando 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 utilizó mucho en inteligencia artificial y aprendizaje automático, 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 {# depthfirstsearch}

Ejemplo de pregunta de entrevista

Compruebe si el gráfico dado está fuertemente conectado o no:

cheque_dfs

Explicación

La primera búsqueda en profundidad (DFS) es otro algoritmo transversal de gráficos, similar a la primera búsqueda en amplitud.

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 hacia abajo en la línea tanto como sea posible.

dfs_search

Una vez que llega al nodo final de esa rama (1), retrocede hasta el primer nodo donde se enfrentó a la posibilidad de cambiar de rumbo (5) y visita toda esa rama, en nuestro caso solo (2).

Luego retrocede nuevamente al nodo (5) y como ya ha visitado los nodos (1) y (2), retrocede a (3) y se redirige a la siguiente rama (8).

El algoritmo continúa atravesando de esta manera hasta que se han visitado todos los nodos 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 un Stack, que es la principal diferencia entre estos dos algoritmos. Una ‘Pila’ sigue una estructura LIFO (Último en entrar, primero en salir), razón por la cual va lo más lejos posible, antes de tener en cuenta 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 a rendimiento.

Echemos un vistazo al pseudocódigo recursivo detrás de la implementación:

1
2
3
4
5
6
dfs(node)
node set visited true

for n in node neighbors
    if n is not visited
    dfs(n)

Comenzamos llamando al algoritmo en el nodo dado y establecemos que es visitado.

Luego verificamos todos los vecinos del nodo 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 vuelve a la parte superior 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 Stack en este ejemplo y me gustaría abordarlo correctamente. Ambos enfoques usan una estructura Stack 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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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 nodo inicial a la Pila. Dado que la pila no está vacía, configuramos el nodo actual para que sea el nodo de inicio 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 nodo “actual” en la siguiente iteración. De esta forma, todos los hijos de este nodo se comprobarán antes que el nodo próximo 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 aprendizaje automático. Estos dos algoritmos son muy comunes y se comparan a menudo.

DFS se usa generalmente para encontrar caminos entre nodos, y especialmente para encontrar caminos para laberintos. DFS también se usa para clasificar topológicamente y encontrar componentes fuertemente conectados.

A* Buscar

Dado el siguiente gráfico, donde el nodo negro es el nodo inicial, los nodos rojos son las paredes y el nodo verde es el nodo objetivo, encuentre el camino más corto al nodo verde:

a_star_search_example

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 caminos de la vida real.

Una* búsqueda se basa en una función de conocimiento y costo heurístico para el nodo dado como una forma de decidir qué nodo 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 coste se calcula como la suma de otras dos funciones:

  • g(x) - La función que representa el costo de moverse desde el nodo inicial a un nodo dado.
  • h(x) - El costo estimado desde el nodo dado hasta el nodo objetivo.

Obviamente, no sabemos el costo exacto del movimiento desde la nota dada hasta el nodo de destino, razón por la cual h(x) también se conoce como "heurística".

El algoritmo siempre elige el nodo con el valor f(x) más 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 estemos de la meta, el valor de f(x) será 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 llegar aumenta la función f(x).

A* Aplicaciones de búsqueda

"¿Dónde podemos usar A* Search?

Este 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 jugadores de IA confían en A* para buscar inteligentemente un camino, rápido y eficiente.

Algoritmo de Dijkstra {#algoritmo de Dijkstra}

Dada la siguiente gráfica ponderada, encuentre el camino más corto entre los vértices A y H.

dijkstra_interview_graph

Explicación

El algoritmo de Dijkstra es un conocido algoritmo de recorrido de gráficos para encontrar el camino más corto desde un nodo/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 nodos.

Dijkstra funciona de una manera ligeramente diferente a los algoritmos anteriores. En lugar de comenzar en el nodo raíz, comienza en el nodo objetivo y retrocede hasta el nodo 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 nodo de destino (más a menudo denominado nodo de origen) hasta todos los demás nodos del gráfico. La dist al nodo de origen es 0 ya que ahí es donde empezamos. Además, la distancia a todos los demás nodos se establece en infinito. A medida que el algoritmo atraviesa el gráfico, la distancia a todos los demás nodos se vuelve a calcular de acuerdo con el nodo actual.
  • Q - Similar a BFS, necesitamos definir un tipo de datos de Cola y llenarlo con todos los nodos 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 nodos visitados, para no volver a visitarlos. Al final, el conjunto contendrá todos los nodos del gráfico.

Echemos un vistazo al pseudocódigo detrás de su implementación:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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 {#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 se basa en gran medida exactamente en Dijkstra y tiene aplicaciones en redes informáticas.

Comparación de BFS, DFS, A* y Dijkstra

Es posible que esto no aparezca como una pregunta de la entrevista, pero sin duda es una pregunta lógica. Hemos cubierto 4 algoritmos diferentes que se utilizan principalmente para el mismo propósito.

"¿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 similares, ofrecen ventajas sobre los demás, según la situación en la que los esté implementando y su caso específico.

Aquí hay 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 activos. BFS perdería demasiado tiempo considerando niveles que no deberían considerarse. 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 estarían ubicados 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, el uso de 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 nodos es el mismo, mientras que el peso/costo real puede variar. ¡Aquí es donde entra en juego Dijkstra!

Dijkstra tiene en cuenta el coste de moverse por un borde. Si el costo de ir en línea recta es mayor que el de dar la vuelta, se dará la vuelta. 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 nodos, 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 el momento, prácticamente obtiene Dijkstra, aunque al revés. Esto hace que A* no corra con avidez hacia la meta, sino en todas direcciones considerando cada uno de los nodos del gráfico, que de nuevo es lo mismo que Dijkstra.

Si está buscando una búsqueda optimizada y resultados que se centren exclusivamente en el objetivo, A* es la opción para usted.

Si está buscando un algoritmo para calcular la ruta más corta entre el punto de inicio y cada uno de los nodos del árbol, que incluye el nodo de destino, Dijkstra es la opción para usted.

Recursos

Si estás buscando una mejor manera de practicar este tipo de preguntas de entrevistas de programación, así como otras, te recomendamos que pruebes un servicio como [Problema de codificación diaria](https://stackabu.se/ problema de codificación diaria). Le enviarán un nuevo problema para resolver todos los días, todos los cuales provienen de las mejores empresas. También puedes saber más aquí si quieres más info.

Conclusión

En este artículo, hemos cubierto las preguntas comunes de la entrevista relacionadas con la estructura de datos del gráfico.

Nuevamente, si está interesado en leer más sobre Preguntas de la entrevista de programación en general, hemos compilado una larga lista de estas preguntas, incluyendo sus explicaciones, implementaciones, representaciones visuales y aplicaciones.