Cuando trabajas con algoritmos de grafos más allá de DFS, BFS y backtracking, te encuentras con estructuras especializadas como heap y trie, y con técnicas como topological sort y Dijkstra que resuelven problemas reales: desde organizar dependencias hasta encontrar el camino más rápido de una ambulancia al hospital. Aquí te explico cómo funcionan y para qué sirven.

¿Qué es un min-heap o max-heap y cuándo usarlo?

Un heap es un árbol especializado que mantiene siempre un orden por prioridad. Es una de las formas más comunes de implementar colas de prioridad por debajo.

Si hablas de un min-heap, el valor más pequeño siempre está arriba, en la raíz. Si hablas de un max-heap, arriba siempre está el más grande. Cuando necesitas sacar un elemento, tomas la cabeza del árbol, y ahí está su utilidad: traer rápido los N elementos más prioritarios, ya sean los más grandes, los más cortos o lo que estés midiendo [02:10].

¿Cuál es la complejidad de insertar en un heap? Insertar un nuevo valor cuesta log N en el peor caso, porque el nuevo elemento debe ubicarse de forma estratégica para mantener el orden de prioridad del árbol.

Por ejemplo, si insertas un 3 en un min-heap donde el 2 sigue siendo la raíz, el 3 se reorganiza para que los hijos del 2 pasen a ser 3 y 4, no 4 y 8. El orden se conserva sin recorrer todo el árbol.

¿Para qué sirve un trie en estructuras de datos?

El trie es otro árbol especializado, pensado para almacenar muchas palabras ocupando menos espacio y permitir búsquedas por prefijo muy rápidas [03:15].

Lo usas cuando necesitas:

• Guardar diccionarios completos de forma compacta.
• Verificar si una palabra es prefijo de otra.
• Buscar palabras dentro de un documento.
• Asignar URLs a servidores web según el prefijo del path.

¿Cómo se organizan las palabras dentro de un trie?

Partes de una raíz, normalmente representada con un asterisco, y desde ahí se ramifican las letras. Cada camino desde la raíz hasta un símbolo de numeral (#) representa una palabra completa.

Imagina que guardas las palabras luz, sol, solté y ser. Luz se forma siguiendo L → U → Z → #. Para sol y solté, el prefijo S → O → L se comparte: si después aparece un #, terminaste en sol; si sigues con T → É → #, formaste solté. Lo mismo ocurre con ser: S → E → R → #.

¿Cómo obtienes todas las palabras que empiezan con cierto prefijo? Recorres el trie hasta el último nodo del prefijo y luego imprimes todos los caminos que salen de ahí hasta cada símbolo de numeral.

Esa propiedad es la que vuelve al trie tan poderoso para autocompletado y búsquedas por prefijo.

¿Qué algoritmos de grafos debo conocer además de DFS y BFS?

Más allá del recorrido básico, hay dos algoritmos que aparecen una y otra vez en problemas reales: topological sort y Dijkstra.

¿Cómo funciona topological sort y para qué se usa?

El topological sort organiza un grafo según sus dependencias, dejando primero lo que debe ocurrir antes [05:30].

Piensa en armar un Lego siguiendo el manual: para colocar una ficha encima, primero debes haber puesto la de abajo. Esa relación de "primero esto, luego aquello" es justo lo que ordena este algoritmo.

Algunas aplicaciones donde encaja perfecto:

• Diseñar el pénsum de una carrera o tu ruta de cursos en Platzi, sabiendo qué temas son requisito de otros.
• Seguir manuales de pasos donde un estado depende del anterior.
• Ordenar palabras según un alfabeto, donde las que empiezan con A van antes que las de B.
• Detectar ciclos en un grafo: si una dependencia nunca se resuelve, hay un ciclo.

¿Qué es Dijkstra y cómo encuentra el camino más corto?

Dijkstra es el algoritmo clásico para encontrar caminos mínimos en un grafo con pesos, es decir, donde cada relación tiene un valor asociado [07:45].

La diferencia con un recorrido simple es que aquí no cuentas cuántos nodos saltas, sino cuánto "cuesta" cada salto. Y ese costo puede representar cosas muy reales: tiempo, distancia, dinero o tráfico.

¿Cuándo conviene usar Dijkstra? Cuando necesitas la ruta más eficiente entre dos puntos en un grafo con pesos, como una ambulancia que debe llegar de una casa al hospital por el camino que tome menos minutos.

Imagina ese escenario: los pesos del grafo son minutos de viaje según el tráfico. Puedes tener rutas de 6 y 2, otra de 6, 1 y 3, otra de 9 y 3, pero la mejor combinación suma 1, 1, 1 y 2, lo que da 5 minutos en total. Esa es la ruta que salva la vida.

Dijkstra evalúa esos pesos sistemáticamente y te entrega el camino óptimo sin que tengas que probar todas las combinaciones a mano.

¿Qué otros algoritmos de grafos vale la pena explorar?

La lista no termina ahí. Existen muchos algoritmos más, cada uno pensado para un tipo de problema específico, y la elección depende de la industria y del reto que estés resolviendo. Algunos los reconocerás solo por el nombre, otros se vuelven herramientas diarias cuando trabajas en optimización, redes, rutas o sistemas de recomendación.

¿Qué algoritmo de grafos te llama más la atención o cuál te gustaría dominar a fondo? Cuéntamelo en los comentarios.