Un programador efectivo necesita una sólida comprensión de las estructuras de datos y los algoritmos. Las entrevistas técnicas a menudo pondrán a prueba sus habilidades de resolución de problemas y pensamiento crítico.
Los gráficos son una de las muchas estructuras de datos importantes en la programación. En la mayoría de los casos, comprender gráficos y resolver problemas basados en gráficos no es fácil.
¿Qué es un gráfico y qué necesitas saber sobre él?
¿Qué es un gráfico?
Un gráfico es una estructura de datos no lineal que tiene nodos (o vértices) con bordes que los conectan. Todos los árboles son subtipos de gráficos, pero no todos los gráficos son árboles, y el gráfico es la estructura de datos a partir de la cual se originaron los árboles.
Aunque puedes construir estructuras de datos en JavaScript y otros lenguajes, puede implementar un gráfico de varias maneras. Los enfoques más populares son listas de borde, listas de adyacencia, y matrices de adyacencia.
los Guía de Khan Academy para representar gráficas es un gran recurso para aprender a representar un gráfico.
Hay muchos tipos diferentes de gráficos. Una distinción común es entre dirigido y no dirigido gráficos; estos surgen mucho en los desafíos de codificación y los usos de la vida real.
Tipos de gráficos
- Gráfico dirigido: Un gráfico en el que todos los bordes tienen una dirección, también conocido como dígrafo.
- Gráfico no dirigido: Un gráfico no dirigido también se conoce como gráfico de dos vías. En gráficos no dirigidos, la dirección de los bordes no importa y el recorrido puede ir en cualquier dirección.
- Gráfico ponderado: Un grafo ponderado es un grafo cuyos nodos y aristas tienen un valor asociado. En la mayoría de los casos, este valor representa el costo de explorar ese nodo o borde.
- Gráfico finito: Un gráfico que tiene un número finito de nodos y aristas.
- Gráfico infinito: Un gráfico que tiene una cantidad infinita de nodos y aristas.
- Gráfico trivial: Un gráfico que tiene un solo nodo y ningún borde.
- gráfico sencillo: Cuando solo un borde conecta cada par de nodos de un gráfico, se llama un gráfico simple.
- Gráfico nulo: Un gráfico nulo es un gráfico que no tiene bordes que conecten sus nodos.
- Multigrafo: En un multigrafo, al menos un par de nodos tienen más de un borde que los conecta. En los multigrafos, no hay bucles automáticos.
- Gráfico completo: Un gráfico completo es un gráfico en el que cada nodo se conecta con todos los demás nodos del gráfico. También es conocido como un gráfico completo.
- Pseudográfico: Un gráfico que tiene un bucle propio aparte de otros bordes del gráfico se denomina pseudográfico.
- Gráfico regular: Un gráfico regular es un gráfico donde todos los nodos tienen grados iguales; es decir, cada nodo tiene el mismo número de vecinos.
- Gráfico conectado: Un gráfico conexo es simplemente cualquier gráfico en el que dos nodos se conectan; es decir, un gráfico con al menos un camino entre cada dos nodos del gráfico.
- Gráfico desconectado: Un gráfico desconectado es el opuesto directo de un gráfico conectado. En un gráfico desconectado, no hay bordes que unen los nodos del gráfico, como en un nulo grafico.
- Gráfico cíclico: Un gráfico cíclico es un gráfico que contiene al menos un ciclo de gráfico (un camino que termina donde comenzó).
- Gráfico acíclico: Un gráfico acíclico es un gráfico sin ciclos en absoluto. Puede ser dirigido o no dirigido.
- Subgrafo: Un subgrafo es un grafo derivado. Es un grafo formado por nodos y aristas que son subconjuntos de otro grafo.
A círculo en un grafo es una arista que parte de un nodo y termina en el mismo nodo. Por lo tanto, un bucle automático es un bucle sobre un solo nodo de gráfico, como se ve en un pseudográfico.
Algoritmos de recorrido de grafos
Al ser un tipo de estructura de datos no lineal, atravesar un gráfico es bastante complicado. Atravesar un gráfico significa atravesar y explorar cada nodo dado que existe un camino válido a través de los bordes. Los algoritmos de recorrido de grafos son principalmente de dos tipos.
- Búsqueda primero en amplitud (BFS): La búsqueda en amplitud es un algoritmo transversal de gráfico que visita un nodo de gráfico y explora sus vecinos antes de pasar a cualquiera de sus nodos secundarios. Aunque puede comenzar a recorrer un gráfico desde cualquier nodo seleccionado, el nodo raíz suele ser el punto de partida preferido.
- Búsqueda en profundidad (DFS): Este es el segundo algoritmo principal de recorrido de grafos. Visita un nodo de gráfico y explora sus nodos secundarios o ramas antes de pasar al siguiente nodo, es decir, profundiza primero antes de ampliarse.
La búsqueda en amplitud es el algoritmo recomendado para encontrar rutas entre dos nodos lo más rápido posible, especialmente la ruta más corta.
La búsqueda en profundidad se recomienda principalmente cuando desea visitar todos los nodos del gráfico. Ambos algoritmos transversales funcionan bien en cualquier caso, pero uno puede ser más simple y más optimizado que el otro en escenarios seleccionados.
Una simple ilustración puede ayudar a comprender mejor ambos algoritmos. Piense en los estados de un país como un gráfico e intente verificar si dos estados, X y Y, estan conectados. Una búsqueda en profundidad podría recorrer casi todo el país sin darse cuenta a tiempo de que Y está a solo 2 estados de distancia de X.
La ventaja de una búsqueda primero en amplitud es que mantiene la proximidad al nodo actual tanto como sea posible antes de pasar al siguiente. Encontrará la conexión entre X y Y en poco tiempo sin tener que recorrer todo el país.
Otra diferencia importante entre estos dos algoritmos es la forma en que se implementan en el código. La búsqueda primero en amplitud es una algoritmo iterativo y hace uso de un cola, mientras que una búsqueda en profundidad generalmente se implementa como un algoritmo recursivo que aprovecha la pila.
A continuación se muestra un pseudocódigo que demuestra la implementación de ambos algoritmos.
Búsqueda primero en amplitud
bfs (Gráfico G, raíz de GraphNode) {
dejar q ser nuevo Cola// marca la raíz como visitada
root.visitado = verdadero// agregar raíz a la cola
q.poner en cola(raíz)
tiempo (q no es vacío) {
dejar ser actual q.dequeue() // elimina el elemento frontal en la cola
for (vecinos n de corriente en G) {
si (norte esno todavía visitado) {
// agregar a la cola, para que también pueda explorar sus vecinos
q.poner en cola(norte)
n.visitado = verdadero
}
}
}
}
Búsqueda en profundidad primero
dfs (Gráfico G, raíz de GraphNode) {
// caso base
si (raíz es nulo) devolver// marca la raíz como visitada
root.visitado = verdadero
for (vecinos n de raíz en G)
si (norte esno todavía visitado)
dfs (G, n) // llamada recursiva
}
Algunos otros algoritmos de recorrido de gráficos se derivan de búsquedas primero en amplitud y primero en profundidad. Los más populares son:
- Búsqueda bidireccional: Este algoritmo es una forma optimizada de encontrar el camino más corto entre dos nodos. Utiliza dos búsquedas primero en amplitud que chocan si hay una ruta.
- Clasificación topológica: Esto se usa en grafos dirigidos para ordenar los nodos en el orden deseado. No puede aplicar una ordenación topológica a gráficos no dirigidos o gráficos con ciclos.
- Algoritmo de Dijkstra: Este también es un tipo de BFS. También se utiliza para encontrar el camino más corto entre dos nodos en un gráfico dirigido ponderado, que pueden tener ciclos o no.
Preguntas de entrevista comunes basadas en gráficos
Los gráficos están entre los más importantes. estructuras de datos que todo programador debe conocer. A menudo surgen preguntas sobre este tema en las entrevistas técnicas, y es posible que encuentre algunos problemas clásicos relacionados con el tema. Estos incluyen cosas como el "juez de la ciudad", el "número de islas" y los problemas del "vendedor ambulante".
Estos son solo algunos de los muchos problemas populares de entrevistas basadas en gráficos. Puedes probarlos en LeetCode, HackerRank, o GeeksforGeeks.
Comprender las estructuras de datos de gráficos y los algoritmos
Los gráficos no solo son útiles para entrevistas técnicas. También tienen casos de uso en el mundo real, como en redes, mapas, y sistemas de aerolíneas para encontrar rutas. También se utilizan en la lógica subyacente de los sistemas informáticos.
Los gráficos son excelentes para organizar datos y ayudarnos a visualizar problemas complejos. Sin embargo, los gráficos solo deben usarse cuando sea absolutamente necesario para evitar la complejidad del espacio o los problemas de memoria.
