Saltar al contenido

Fundamentos de grafos

Lección 1 de 16 · 5 min

Fundamentos de grafos

Paso 1 de 7

Un grafo son cosas más las conexiones entre ellas. Esa es toda la definición.

La idea

Un grafo son nodos unidos por aristas. Esa es toda la definición: el array (arreglo) y la lista enlazada (linked list) solo le agregan reglas encima. Las aristas pueden ser no dirigidas (un vínculo en ambos sentidos) o dirigidas (de un solo sentido). El grado de un nodo es simplemente cuántas aristas lo tocan.

Ejemplo del mundo real

Una molécula es un grafo que puedes sostener en la mano. Los átomos son los nodos, los enlaces químicos son las aristas y, cuando todos los enlaces son simples, la valencia de un átomo es su grado: el carbono acepta cuatro enlaces; el hidrógeno, exactamente uno. Los químicos dibujan estructuras en lugar de fórmulas porque son las conexiones, no la cantidad de átomos, las que deciden qué hace la sustancia.

El código

Te toca

¿Qué imprime esto?

g = {"A": ["B", "C"], "B": ["A"], "C": ["A"]}
print(len(g), sum(len(v) for v in g.values()) // 2)

Mini quiz

1 / 3

¿Cuáles son los dos ingredientes de todo grafo?