Documentación

BFS (Breadth-First Search)

El algoritmo BFS (Breadth-First Search) recorre el grafo por niveles a partir de un vértice origen, visitando primero todos los vértices adyacentes antes de avanzar a niveles más profundos.

Este tipo de recorrido garantiza que la primera vez que se alcanza un vértice se ha seguido el camino con menor número de aristas desde el origen. Por este motivo, BFS permite calcular distancias mínimas en grafos no ponderados y es especialmente útil para estudiar la conectividad y la estructura general del grafo.

Requisitos de ejecución

• No tiene restricciones

Ejecución en MadnessMad

• Se pide el nodo de origen.
• Se anima por niveles.
• Muestra el orden de visita en el panel de información.

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

DFS (Depth-First Search)

DFS explora el grafo siguiendo un camino hasta donde sea posible, avanzando de vértice en vértice sin retroceder hasta que no quedan opciones disponibles.

Cuando alcanza un vértice sin vecinos no visitados, el algoritmo retrocede para continuar la exploración desde el último punto pendiente. Este comportamiento permite analizar la estructura del grafo, detectar ciclos y descomponerlo en componentes conexas, además de servir como base para algoritmos más avanzados.

Requisitos de ejecución

• No tiene restricciones

Ejecución en MadnessMad

• Se pide el nodo de origen.
• Se anima arista por arista.
• Muestra el orden de visita en el panel de información.

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

Dijkstra

El algoritmo de Dijkstra calcula los caminos mínimos desde un vértice origen al resto de vértices mediante un proceso iterativo de relajación de aristas.

Garantiza resultados óptimos siempre que los pesos sean no negativos, siendo uno de los algoritmos fundamentales para el cálculo de rutas y costes mínimos.

Requisitos de ejecución

• Grafo ponderado (si no lo es todas las aristas valen 1)
• Pesos no negativos

Ejecución en MadnessMad

• Se pide el nodo de origen.
• Se pide el nodo destino, se puede seleccionar también todos.
• Muestra el camino (o caminos) de la forma V₁ → V₂ → … → V_n.
• También muestra el peso de cada camino.

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

Bellman–Ford

Bellman–Ford calcula caminos mínimos repitiendo la relajación de todas las aristas del grafo, permitiendo trabajar con pesos negativos.

Además, es capaz de detectar ciclos de coste negativo, lo que lo hace especialmente útil para validar la coherencia de grafos ponderados.

Requisitos de ejecución

• Grafo ponderado (si no lo es todas las aristas valen 1)
• No se permiten ciclos negativos

Ejecución en MadnessMad

• Se pide el nodo de origen.
• Se pide el nodo destino, se puede seleccionar también todos.
• Muestra el camino (o caminos) de la forma V₁ → V₂ → … → V_n.
• También muestra el peso de cada camino.

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

Kruskal

El algoritmo de Kruskal construye un árbol de expansión mínima o máxima seleccionando aristas de menor o mayor peso y añadiéndolas siempre que no formen ciclos.

Puede aplicarse a grafos incluso si no son conexos. En ese caso, el resultado es un bosque de expansión, con un árbol por cada componente conexa, optimizando el coste total en cada una de ellas.

Requisitos de ejecución

• Grafo ponderado
• Grafo no dirigido

Ejecución en MadnessMad

• Se da a elegir entre árbol maximal o minimal.
• Se pintan todas las aristas del árbol resultante.
• Muestra el peso total del árbol (o bosque) en el panel de información.

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

Edmonds2 (Emparejamiento máximo)

El algoritmo Edmonds 2 calcula un emparejamiento en un grafo no dirigido y ponderado, maximizando siempre el número de aristas emparejadas.

Una vez alcanzada la máxima cardinalidad posible, el algoritmo optimiza el peso total del emparejamiento. En modo MAX se selecciona el emparejamiento de mayor peso, y en modo MIN el de menor peso, sin reducir en ningún caso el número de parejas.

Esta prioridad se garantiza mediante una reducción del problema a un emparejamiento perfecto, evitando que la optimización del peso afecte al tamaño del emparejamiento.

Requisitos de ejecución

• Grafo ponderado
• Grafo no dirigido
• Al menos dos vértices y una arista

Ejecución en MadnessMad

• Se da a elegir entre peso máximo o mínimo.
• Se pintan las aristas resultantes.
• Muestra la cardinalidad y peso total del acoplamiento.
• También da información de las aristas escogidas.

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

Hierholzer

El algoritmo de Hierholzer encuentra un camino o ciclo euleriano recorriendo todas las aristas del grafo exactamente una vez.

Comienza construyendo un ciclo inicial y, mientras existan vértices del recorrido con aristas sin visitar, genera nuevos ciclos que se insertan en el recorrido ya construido hasta obtener una única trayectoria que incluye todas las aristas.

Requisitos de ejecución

• Grafo euleriano

Ejecución en MadnessMad

• Si es un ciclo euleriano la animación muestra el camino euleriano cerrado.
• En el panel de información se muestra la ruta completa.

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

Cartero Chino

El algoritmo del cartero chino busca un recorrido cerrado de coste mínimo que pase por todas las aristas del grafo al menos una vez.

Si el grafo no es euleriano, el algoritmo identifica los vértices que impiden la existencia de un ciclo euleriano y añade recorridos auxiliares mínimos para equilibrarlo. Una vez equilibrado, se aplica un recorrido euleriano, integrando las aristas originales y las añadidas en una única trayectoria cerrada.

Requisitos de ejecución

• Grafo ponderado (si no lo es todas las aristas valen 1)
• Grafo conexo
• Grafo fuertemente conexo en grafos dirigidos

Ejecución en MadnessMad

• Muestra la animación del ciclo euleriano resultante.
• Las aristas auxiliares se pintan de verde.
• En el panel de información se muestra la ruta completa.

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

Ford–Fulkerson

El algoritmo de Ford–Fulkerson calcula el flujo máximo entre un nodo origen y un nodo destino en una red mediante la búsqueda de caminos aumentantes.

Ajusta progresivamente las capacidades residuales y sirve como base para el estudio de redes de flujo y optimización de recursos.

Requisitos de ejecución

• Grafo dirigido y débilmente conexo
• Aristas con peso no negativo
• Grafo ponderado

Ejecución en MadnessMad

• Se pide el nodo fuente.
• Se pide el nodo sumidero.
• Se muestra una animación camino por camino de flujo.
• En el panel se muestra el flujo máximo de la red.
• También se muestra capacidad y flujo arista por arista.

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

Hamilton (bajo peso)

Este algoritmo busca un ciclo hamiltoniano de bajo peso mediante heurísticas (por ende puede fallar), priorizando aristas de menor coste sin garantizar una solución óptima global.

En MadnessMad se ofrecen dos estrategias: un enfoque voraz (Greedy), que avanza eligiendo localmente la mejor arista disponible, y un enfoque basado en árbol de expansión mínima (MST), que utiliza la estructura del árbol para guiar la construcción del ciclo.

Ambos métodos reducen significativamente el coste computacional frente a la búsqueda exhaustiva, siendo adecuados para grafos de mayor tamaño cuando se desea una solución razonable en tiempo práctico.

Requisitos de ejecución

• Grafo ponderado (si no lo es todas las aristas valen 1)
• Grafo no dirigido
• Grafo conexo
• Aristas con peso no negativo

Ejecución en MadnessMad

• Se da a elegir entre ejecución "Greedy" y "MST-based".
• Se pide el nodo de origen.
• Se muestra una animación para el camino hamiltoniano (si se encuentra).
• En el panel se muestra el peso total y la ruta del camino.

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

Hamilton (mínimo peso)

Calcula el camino hamiltoniano de menor coste evaluando todas las combinaciones posibles mediante fuerza bruta.

Garantiza la solución óptima, aunque su complejidad exponencial lo limita a grafos pequeños.

Requisitos de ejecución

• Grafo ponderado (si no lo es todas las aristas valen 1)
• Grafo pequeño (hasta 10 vértices)
• Grafo no dirigido
• Grafo conexo
• Aristas con peso no negativo

Ejecución en MadnessMad

• Se pide el nodo de origen.
• Se muestra una animación para el camino hamiltoniano.
• En el panel se muestra el peso total y la ruta del camino.

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

Hopcroft–Tarjan

El algoritmo de Hopcroft–Tarjan identifica vértices de corte y aristas puente en grafos no dirigidos.

Permite analizar la robustez y los puntos críticos de la estructura del grafo.

Requisitos de ejecución

• Grafo no dirigido

Ejecución en MadnessMad

• Se muestran pintadas las aristas y vértices de corte.

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

Centralidad de grado

La centralidad de grado mide la importancia de un vértice en función del número de conexiones directas que tiene con otros vértices del grafo.

Los vértices con mayor grado suelen representar nodos altamente conectados, lo que en redes sociales se interpreta como actores con gran nivel de interacción o influencia local.

Requisitos de ejecución

• Sin restricciones.

Ejecución en MadnessMad

• En grafos no dirigidos, se usan las componentes conexas clásicas.
• En grafos dirigidos, se emplean componentes débilmente conexas.
• El resultado se agrupa por componentes.
• Para cada nodo: V₁ → Grado (g) · Normalizado (n).

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

Centralidad de intermediación (Betweenness)

La centralidad de intermediación cuantifica cuántos de los caminos mínimos entre pares de vértices pasan por un vértice dado.

Un valor alto indica que el vértice actúa como punto de paso o intermediario clave dentro de la red, siendo fundamental para la comunicación o el flujo de información.

Requisitos de ejecución

• Grafo ponderado (si no lo es todas las aristas valen 1)
• No se admiten pesos negativos.

Ejecución en MadnessMad

• Para cada nodo: V₁ → CB = (n) · CB Normalizado (n).

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

Centralidad de cercanía

La centralidad de cercanía mide lo cerca que está un vértice del resto de vértices del grafo, considerando la distancia mínima media hacia todos ellos.

Los vértices con mayor cercanía pueden alcanzar rápidamente al resto de la red, lo que los hace relevantes en procesos de difusión o propagación.

Requisitos de ejecución

• Grafo ponderado (si no lo es todas las aristas valen 1)
• El grafo debe ser no dirigido.
• No se admiten pesos negativos.

Ejecución en MadnessMad

• El resultado se agrupa por componentes conexas.
• S = Suma distancias C = Centricidad.
• Para cada nodo: V₁ → S: (n) · C: (n).

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

Centralidad de excentricidad

La excentricidad de un vértice se define como la mayor distancia mínima desde dicho vértice hasta cualquier otro vértice del grafo.

Permite identificar vértices periféricos o centrales, y es una métrica clave para el cálculo del radio y el diámetro del grafo.

Requisitos de ejecución

• El grafo debe ser no dirigido.
• No se admiten pesos negativos.

Ejecución en MadnessMad

• Grafo ponderado (si no lo es todas las aristas valen 1)
• El resultado se agrupa por componentes conexas.
• E = Excentricidad C = Centricidad.
• Para cada nodo: V₁ → E: (n) · C: (n).

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

Clustering local

El coeficiente de clustering local mide el grado en el que los vecinos de un vértice están conectados entre sí.

Valores altos indican la presencia de comunidades locales densamente conectadas alrededor del vértice analizado.

Requisitos de ejecución

• El grafo debe ser no dirigido.

Ejecución en MadnessMad

• CCLC = Coeficiente de clustering local, d = grado.
• Para d(V) < 2 el CCLC = 0.
• Para cada nodo: V₁ → d = n, CCLC = n (normalizado).

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

Clustering global

El clustering global evalúa el nivel de agrupamiento del grafo completo, midiendo la proporción de triángulos presentes respecto a los posibles.

Ofrece una visión general del grado de cohesión y estructura comunitaria de la red.

Requisitos de ejecución

• El grafo debe ser no dirigido.

Ejecución en MadnessMad

• Ornamentación no disponible.
• El resultado es Cg = n. Cg = Clustering global.

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

Clustering medio

El clustering medio corresponde a la media de los coeficientes de clustering local de todos los vértices del grafo.

Resume el nivel general de agrupamiento local de la red en un único valor representativo.

Requisitos de ejecución

• El grafo debe ser no dirigido.

Ejecución en MadnessMad

• Ornamentación no disponible.
• El resultado es C = n. C = Clustering medio.

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

Alcance medio

El alcance medio mide la distancia media entre pares de vértices alcanzables dentro del grafo.

Es una métrica global relacionada con la eficiencia de la red y la facilidad de conexión entre sus componentes.

Requisitos de ejecución

• Grafo ponderado (si no lo es todas las aristas valen 1)
• Si el grafo es dirigido tiene que ser fuertemente conexo.
• El grafo debe ser conexo
• No deben existir ciclos negativos

Ejecución en MadnessMad

• Ornamentación no disponible.
• El resultado es AM(G) = n. AM(G) = alcance medio del grafo.

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

Diámetro

El diámetro del grafo es la mayor distancia mínima entre cualquier par de vértices alcanzables.

Representa el tamaño efectivo de la red y el peor caso de separación entre nodos.

Requisitos de ejecución

• Grafo ponderado (si no lo es todas las aristas valen 1)
• Si el grafo es dirigido tiene que ser fuertemente conexo.
• El grafo debe ser conexo
• No deben existir ciclos negativos

Ejecución en MadnessMad

• Ornamentación no disponible.
• El resultado es Diámetro = n.

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

PageRank

PageRank asigna a cada vértice un valor de importancia que depende tanto del número de enlaces entrantes como de la relevancia de los vértices que los originan. La idea central es que un vértice es importante si recibe enlaces desde otros vértices que también lo son, propagando la importancia a lo largo del grafo dirigido.

En MadnessMad, el algoritmo se implementa mediante un proceso iterativo basado en el modelo del navegante aleatorio. En cada iteración, parte de la importancia se distribuye a través de las aristas salientes de cada vértice y otra parte se redistribuye globalmente mediante el mecanismo de teletransporte (damping factor), que evita bloqueos y garantiza la convergencia incluso en presencia de vértices sin salidas. Este enfoque permite identificar nodos influyentes en redes dirigidas complejas como la web, redes de citas o grafos de dependencia.

Requisitos de ejecución

• Grafo ponderado (si no lo es todas las aristas valen 1)
• El grafo debe ser dirigido.
• Pesos no negativos.

Ejecución en MadnessMad

• Para cada nodo: V₁: n.
• n ∈ (0,1) y ∑ n = 1

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

Información del árbol

El algoritmo analiza la estructura del grafo para comprobar si es acíclico. Si se detectan ciclos, el grafo no se considera un bosque.

En caso de ser acíclico, el algoritmo identifica las componentes conexas que forman árboles, calcula su número y enumera los vértices que pertenecen a cada uno de ellos.

Si existe una única componente conexa no trivial y no hay vértices aislados, el grafo se clasifica como un árbol. En caso contrario, se obtiene un bosque junto con la lista de vértices aislados.

Requisitos de ejecución

• El grafo debe ser no dirigido.

Ejecución en MadnessMad

• Indica si el grafo es un árbol un bosque o es cíclico.
• En caso de ser un bosque, muestra sus componentes.

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

Mostrar hojas

Si el grafo es acíclico, se identifican los vértices hoja de cada árbol. Un vértice hoja es aquel que tiene grado uno dentro de su componente.

Si el grafo no es un bosque o no existen vértices hoja, el algoritmo no produce resultados.

Requisitos de ejecución

• El grafo debe ser no dirigido.
• El grafo debe ser un bosque.

Ejecución en MadnessMad

• Pinta las hojas del grafo en el canvas.
• Muestra las hojas agrupadas por árbol en el panel de información.

Recursos adicionales
Ver ejecución del algoritmo (YouTube)

LCA (Lowest Common Ancestor)

El algoritmo LCA (ancestro común más bajo) se aplica sobre grafos no dirigidos que forman un bosque. Su objetivo es encontrar el vértice más profundo que es ancestro común de un conjunto de vértices seleccionados, dado un nodo raíz.

A partir del nodo raíz, el algoritmo construye la relación padre–hijo mediante un recorrido en profundidad y calcula los ancestros de cada vértice seleccionado. El LCA se obtiene como el ancestro común situado a mayor profundidad.

Requisitos de ejecución

• El grafo debe ser no dirigido.
• El grafo debe ser un bosque (no contener ciclos).
• Deben seleccionarse al menos dos vértices.

Ejecución en MadnessMad

• Selecciona al menos 2 nodos.
• Ejecuta el algoritmo.
• Selecciona el nodo raíz.
• Se indica el ancestro común más bajo encontrado o informa si no existe.

Recursos adicionales
Ver explicación del algoritmo LCA (YouTube)

Altura del árbol

El algoritmo calcula la altura de un árbol a partir de un nodo raíz indicado. La altura se define como el número máximo de aristas en el camino más largo desde la raíz hasta una hoja.

Para ello, se realiza un recorrido en profundidad desde la raíz, explorando todas las ramas del árbol y manteniendo la mayor profundidad alcanzada.

Requisitos de ejecución

• El grafo debe ser no dirigido.
• El grafo debe ser un bosque (no contener ciclos).

Ejecución en MadnessMad

• Selecciona el nodo raíz.
• Se muestra la raíz utilizada y el valor de la altura.

Recursos adicionales
Ver explicación del cálculo de la altura de un árbol (YouTube)

Balance del árbol

El algoritmo calcula el balance de un árbol a partir de un nodo raíz indicado. El balance de un nodo mide la diferencia entre las alturas de sus subárboles y permite detectar descompensaciones estructurales.

Para cada nodo se calcula la altura de su subárbol y su valor de balance. El balance se define como la diferencia entre la mayor y la menor altura de los subárboles hijos, considerando casos con cero o un solo hijo.

Requisitos de ejecución

• El grafo debe ser no dirigido.
• El grafo debe ser un bosque (no contener ciclos).

Ejecución en MadnessMad

• Se solicita un nodo raíz para el análisis.
• Se muestra una lista ordenada de nodos con su balance, altura de subárbol y número de hijos.

Recursos adicionales
Ver explicación del balance de árboles (YouTube)

Centro del árbol

El algoritmo del centro del árbol identifica el vértice, o par de vértices, que minimiza la distancia máxima al resto de nodos del árbol. Este concepto permite caracterizar el punto más equilibrado de la estructura.

Para su cálculo, el algoritmo obtiene el diámetro del árbol, definido como el camino más largo entre dos hojas. El centro se corresponde con el punto medio de dicho camino. Si el diámetro tiene longitud par, existe un único centro; si es impar, existen dos.

Requisitos de ejecución

• El grafo debe ser no dirigido.
• El grafo debe ser un árbol (una única componente conexa).
• No deben existir vértices aislados.

Ejecución en MadnessMad

• Determina el centro o centros resultantes.
• Muestra la longitud y el camino del diámetro.

Recursos adicionales
Ver explicación del centro del árbol (YouTube)

Ajedrez (PGN) → árbol

Una partida de ajedrez puede representarse como un árbol de variantes, donde cada jugada corresponde a un nodo y cada transición entre jugadas se modela como una arista. La línea principal y sus variantes, junto con sus subvariantes, generan una estructura ramificada que alterna turnos de blancas y negras.

Esta representación permite analizar la partida desde un punto de vista estructural, facilitando la visualización de variantes, profundidades y bifurcaciones en el juego. El resultado es un grafo no dirigido y no ponderado que refleja la progresión de la partida.

Requisitos de ejecución

• Disponer de un PGN válido o de un enlace a una partida de Lichess.

Ejecución en MadnessMad

• Seleccionar la opción PGN y pegar el texto de la partida.
• O bien seleccionar Lichess e introducir el enlace de la partida.
• El grafo se genera automáticamente como un árbol de variantes con la notación de las jugadas.
• Cada nodo es blanco o negro en función de la jugada.

Recursos adicionales
Ver ejemplo de partida convertida en árbol (YouTube)