Algoritmos de Grafos

Explora un grafo nivel por nivel, visitando todos los vértices en la profundidad actual antes de avanzar más profundo. Usa una cola y es ideal para encontrar caminos más cortos en grafos no ponderados. Las aplicaciones incluyen resolución de laberintos, análisis de redes sociales y encontrar conexiones entre nodos.

Explora un grafo yendo lo más profundo posible a lo largo de cada camino antes de retroceder. Se implementa usando una pila o recursión, lo que lo hace natural para problemas recursivos. Se usa para búsqueda de caminos, detección de ciclos, ordenamiento topológico y generación de laberintos.

Encuentra los caminos más cortos desde un vértice fuente único a todos los demás vértices en un grafo ponderado. Impulsa sistemas de navegación GPS y protocolos de enrutamiento de redes. Funciona eficientemente con pesos de arista no negativos usando un enfoque codicioso con una cola de prioridad.

Un algoritmo de búsqueda best-first que encuentra el camino más corto usando heurísticas. Combina el algoritmo de Dijkstra y la búsqueda codiciosa best-first usando f(n) = g(n) + h(n). Ampliamente utilizado en juegos, robótica y navegación GPS para búsqueda eficiente de caminos.

Encuentra el Árbol de Expansión Mínima (MST) de un grafo no dirigido ponderado. Usa un enfoque codicioso ordenando aristas por peso y agregándolas si no crean un ciclo. Emplea Union-Find para detección eficiente de ciclos. Esencial para diseño de redes y agrupamiento.

Encuentra el Árbol de Expansión Mínima (MST) haciendo crecer un árbol desde un vértice inicial. Siempre agrega la arista de peso mínimo que conecta un vértice en el árbol con uno fuera. Usa una cola de prioridad para selección eficiente de aristas. Ideal para grafos densos.

Ordena vértices de un Grafo Acíclico Dirigido (DAG) de modo que para cada arista u→v, u viene antes de v. Usa enfoque basado en DFS. Esencial para resolución de dependencias, sistemas de construcción y programación de cursos.

Algoritmo de Google para clasificar páginas web por estructura de enlaces. Calcula puntuaciones de importancia iterativamente.

También conocido como el algoritmo de la 'tortuga y la liebre', esta elegante técnica detecta ciclos en listas enlazadas o secuencias usando espacio O(1). Usa dos punteros que se mueven a diferentes velocidades; si hay un ciclo, eventualmente se encontrarán. Esencial para detectar bucles infinitos, analizar estructuras de grafos y validar la integridad de los datos.

Algoritmo de camino más corto desde un origen único que maneja pesos negativos y detecta ciclos negativos. Relaja todas las aristas V-1 veces para garantizar distancias correctas incluso con pesos negativos. Esencial para detección de arbitraje de divisas, enrutamiento de redes con costos variados y situaciones donde el algoritmo de Dijkstra falla. Intercambia velocidad por flexibilidad.

Algoritmo de caminos más cortos entre todos los pares que calcula distancias entre cada par de vértices en tiempo O(V³). Usa programación dinámica con lógica central elegante de tres líneas. Maneja pesos negativos y proporciona cierre transitivo. Ideal para grafos densos, análisis de redes y cuando se necesitan todas las distancias por pares.

Algoritmo codicioso que construye un árbol de expansión mínima agregando aristas en orden de peso creciente, usando union-find para evitar ciclos. Eficiente para grafos dispersos con complejidad de tiempo O(E log E). Las aplicaciones incluyen diseño de redes, agrupamiento, algoritmos de aproximación y comprensión de pruebas de corrección codiciosa.

Algoritmo codicioso que hace crecer un árbol de expansión mínima agregando repetidamente la arista más barata que conecta el árbol a un nuevo vértice. Usa una cola de prioridad para eficiencia con tiempo O(E log V). Preferido para grafos densos y aplicaciones en tiempo real como difusión de redes y diseño de circuitos.