Graphs · Grafos
Graphs
- A graph is a set of nodes (also called vertices) joined by edges (connections).
- Graphs model networks: friends, roads between cities, links between web pages.
- A tree is really a special graph; a general graph can have cycles and many links per node.
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.
Representing a graph: adjacency list
- One common way is an adjacency list: a dictionary mapping each node to its list of neighbours.
graph["A"]is the list of nodes directly connected toA.- This is compact when each node has only a few connections.
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']
Adding an edge
- In an undirected graph, an edge
A—Bgoes both ways. - So adding it means appending
BtoA's list andAtoB's list. - If a node is new, start it with an empty list first.
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']}
Walking the neighbours
- To explore from a node, you read its neighbour list and visit each one.
- A node that is not in the graph has no neighbours — return an empty list, not an error.
- This neighbour lookup is the first step of bigger jobs like searching the whole graph.
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.
Directed vs undirected
- In an undirected graph an edge works both ways (a friendship).
- In a directed graph an edge points one way only (a one-way street, a "follows" link).
- For directed edges you would append in one direction only.
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.
Common mistakes
- A graph is nodes joined by edges; an edge can be one-way or two-way.
- A tree is a graph with no cycles — do not confuse the two.
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.
Now you try
- Build the adjacency-list operations:
add_edge,neighbours, andcount_edges. - Each task checks your function on a small graph.
- Press Check answer to test it.
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.
Write add_edge(graph, a, b) for an undirected graph stored as a dict of neighbour lists. Append b to · hasta graph[a] and · y a to · hasta graph[b]. If a node is not in the graph yet, give it an empty list [] first. Change the dict in place. · 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.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
Write neighbours(graph, node) that returns the list of nodes directly connected to node. If node is not in the graph, return an empty list [] (do not raise an error). · 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).
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
Write count_edges(graph) for an undirected graph: count how many edges it has. Add up the lengths of every neighbour list, then divide by 2 (each edge is stored in both nodes' lists). Example: a triangle A–B–C has 3 edges. · 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.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.