Grafos
Gráficos
- Un gráfico es un conjunto de nodos (también llamados vértices) unidos por aristas (conexiones).
- Los gráficos modelan redes: amigos, carreteras entre ciudades, enlaces entre páginas web.
- Un árbol es en realidad un gráfico especial; un gráfico general puede tener ciclos y múltiples enlaces por nodo.
Representación de un gráfico: lista de adyacencia
- Una forma común es una lista de adyacencia: un diccionario que mapea cada nodo a su lista de vecinos.
graph["A"]es la lista de nodos directamente conectados aA.- Esto es compacto cuando cada nodo tiene solo unas pocas conexiones.
# A graph as a dict: each node maps to its list of neighbours
graph = {
"A": ["B", "C"],
"B": ["A"],
"C": ["A"],
}
print(graph["A"]) # ['B', 'C'] -- A connects to B and C
print(graph["B"]) # ['A']
Agregar una arista
- En un gráfico no dirigido, una arista
A—Bfunciona en ambos sentidos. - Por lo tanto, agregarla implica añadir
Ba la lista deAyAa la lista deB. - Si un nodo es nuevo, primero créalo con una lista vacía.
def add_edge(graph, a, b):
if a not in graph:
graph[a] = []
if b not in graph:
graph[b] = []
graph[a].append(b)
graph[b].append(a)
graph = {}
add_edge(graph, "A", "B")
add_edge(graph, "A", "C")
print(graph) # {'A': ['B', 'C'], 'B': ['A'], 'C': ['A']}
Recorrer los vecinos
- Para explorar desde un nodo, lees su lista de vecinos y visitas cada uno.
- Un nodo que no está en el gráfico no tiene vecinos — devuelve una lista vacía, no un error.
- Esta búsqueda de vecinos es el primer paso de tareas más grandes como buscar todo el gráfico.
Dirigido vs no dirigido
- En un gráfico no dirigido, una arista funciona en ambos sentidos (una amistad).
- En un gráfico dirigido, una arista apunta en una sola dirección (una calle de sentido único, un enlace de "seguir").
- Para aristas dirigidas, solo apendarías en una dirección.
Errores comunes
- Un gráfico son nodos unidos por aristas; una arista puede ser de un solo sentido o de doble sentido.
- Un árbol es un gráfico sin ciclos — no los confundas.
Ahora tú intentarlo
- Construye las operaciones de lista de adyacencia:
add_edge,neighboursycount_edges. - Cada tarea verifica tu función en un gráfico pequeño.
- Presiona Check answer para probarlo.
Dificultad 5/5 · 400 monedas + un pequeño bono en el primer intento de hoy
Escribe add_edge(graph, a, b) para un grafo no dirigido almacenado como un diccionario de listas de vecinos. Añade b a graph[a] y a a graph[b]. Si un nodo aún no está en el grafo, dale primero una lista vacía []. Modifica el diccionario in situ.
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 5/5 · 400 monedas + un pequeño bono en el primer intento de hoy
Escribe neighbours(graph, node) que devuelva la lista de nodos directamente conectados a node. Si node no está en el grafo, devuelve una lista vacía [] (no lances un error).
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 5/5 · 400 monedas + un pequeño bono en el primer intento de hoy
Escribe count_edges(graph) para un grafo no dirigido: cuenta cuántas aristas tiene. Suma las longitudes de cada lista de vecinos y divide entre 2 (cada arista se almacena en las listas de ambos nodos). Ejemplo: un triángulo A–B–C tiene 3 aristas.
Haz clic en Ejecutar para ver la salida aquí.