Conectar cosas que no entran en una fila ni en una jerarquía: cualquier nodo se puede conectar con cualquier otro.
Con solo 8 ramos y sus prerrequisitos, probar combinaciones a ciegas hasta encontrar un orden válido es un desastre. Con grafos, el mismo problema se resuelve revisando cada ramo una sola vez.
con los ~40 ramos reales de una carrera, la fuerza bruta tendría que probar hasta 40! combinaciones — más que átomos hay en la Tierra. Por eso necesitamos una estructura mejor.
Un grafo es un conjunto de nodos (o vértices) conectados por aristas. A diferencia de un árbol, no hay una raíz fija, un nodo puede conectarse con cualquier otro, y hasta se pueden formar vueltas (ciclos).
nodos = A, B, C, D, E · aristas = las líneas que los conectan (fíjate que A y C ya forman una vuelta)
En un grafo no dirigido, las conexiones van en ambos sentidos (amistad). En uno dirigido, cada arista tiene un sentido (prerrequisito → ramo).
En un grafo, puedes volver al nodo desde donde empezaste. A eso se le llama ciclo. En un árbol esto es imposible: no hay forma de bajar y volver a subir al mismo nodo.
A → B → C → A: volvemos a A sin repetir ninguna arista. Esta vuelta es justo lo que hace que el problema de los ramos no se pueda resolver con un árbol: un ramo podría depender, indirectamente, de un camino que pasa por sí mismo.
La forma más simple de guardar un grafo en código: un diccionario donde cada nodo apunta a la lista de nodos con los que se conecta.
exactamente la misma idea que usamos para los prerrequisitos: {"Algoritmos": ["EstructuraDatos", "Algebra"]} ya era un grafo, sin que lo llamáramos así.
BFS (anchura) visita primero todos los vecinos cercanos, nivel por nivel. DFS (profundidad) se mete lo más lejos posible por un camino antes de volver. El número en cada nodo es el orden de visita.
esto conecta con lo que ya vimos: BFS usa una cola (FIFO) para decidir a quién visitar después. DFS usa una pila (LIFO) — o recursión, que por dentro funciona igual.
Ramos = nodos. Prerrequisito → ramo = arista dirigida. Recorrer el grafo respetando las flechas nos da un orden topológico: un orden válido para tomar todos los ramos.
| Árbol | Grafo | |
|---|---|---|
| Ciclos | No puede haber | Pueden existir |
| Raíz | Siempre tiene una | No necesariamente |
| Conexiones | Un nodo, varios hijos, un solo padre | Cualquier nodo con cualquier otro |
| Ejemplo | Carpetas de un computador | Red social, mapa de calles, malla curricular |
todo árbol es, en el fondo, un grafo especial: uno sin ciclos y con una raíz. Por eso lo que ya sabían de árboles (nodos, recorridos, recursividad) se traslada casi directo.
Grafo: nodos conectados por aristas, sin jerarquía fija y permitiendo ciclos.
Dirigido / no dirigido: las aristas pueden tener un sentido único o ir en ambos.
BFS / DFS: dos formas de recorrer un grafo — por niveles (con una cola) o en profundidad (con una pila o recursión).
Orden topológico: recorrer un grafo dirigido sin ciclos respetando las flechas, para resolver problemas como el de los prerrequisitos.