Grafos: representación
Qué es un grafo (dirigido vs no dirigido) y sus representaciones: nodos, lista de adyacencia y matriz de adyacencia, con pesos y operaciones básicas.
hub
¿Qué es un grafo?
Un grafo es un conjunto de nodos (también llamados vértices) y las relaciones entre ellos (las aristas).
Los grafos generalizan estructuras que ya conoces: una lista ligada es un grafo lineal y un árbol es un grafo jerárquico. En un grafo general no hay restricciones sobre cómo se conectan los vértices.
Dirigidos vs no dirigidos
- No dirigido: las relaciones son simétricas. Si
Ase relaciona conB, entoncesBse relaciona conA. Ejemplo: la amistad en Facebook. - Dirigido: las relaciones tienen orientación. Que
Aapunte aBno implica queBapunte aA. Ejemplo: seguir a alguien en Instagram.
Cargando Quiz...
data_object
Representación con nodos
La forma más natural: una clase Nodo que guarda su valor y una lista de sus vecinos (los nodos con los que se relaciona directamente).
python
class Nodo: def __init__(self, valor): self.valor = valor self.vecinos = [] def agregar_vecino(self, nodo): self.vecinos.append(nodo)En un grafo no dirigido, una conexión (a, b) se guarda dos veces: b en los vecinos de a, y a en los vecinos de b.
Esta representación es intuitiva pero dispersa la información del grafo entre muchos objetos Nodo, lo que dificulta operaciones globales (como recorrer todos los vértices).
Observación
Cargando Quiz...
schema
Lista de adyacencia
Se guarda un diccionario donde cada llave es un vértice y su valor es la lista (o conjunto) de sus vecinos.
python
grafo_no_dirigido = { 1: [2], 2: [1, 3], 3: [2, 4, 5], 4: [3, 5], 5: [3, 4],} print(list(grafo_no_dirigido.keys())) # vértices: [1, 2, 3, 4, 5]print(grafo_no_dirigido[3]) # vecinos de 3: [2, 4, 5]Ventaja: encontrar un vértice y obtener sus vecinos es directo (acceso por llave del diccionario). Es muy económica en espacio cuando hay pocas aristas.
Cargando Quiz...
calculate
Matriz de adyacencia
Una matriz N x N (con N = número de vértices). La celda [i][j] vale 1 si hay una arista del vértice i al j, y 0 si no. En Python: una lista de listas.
python
grafo_no_dirigido = [ [0, 1, 0, 0, 0], [1, 0, 1, 0, 0], [0, 1, 0, 1, 1], [0, 0, 1, 0, 1], [0, 0, 1, 1, 0],]# ¿Hay arista del vértice 2 al 3? (índices desde 0)print(grafo_no_dirigido[1][2]) # 1 -> síEn un grafo no dirigido la matriz es simétrica; en uno dirigido no necesariamente.
Lista vs matriz: la matriz facilita preguntar si dos vértices están conectados (mirar una celda), pero gasta N×N de espacio. Con pocas aristas, la lista de adyacencia es mucho más eficiente en memoria.
Comparación
Cargando Quiz...
tune
Pesos y operaciones básicas
Pesos en las aristas
Podemos asociar un valor a cada arista (distancia, tiempo, costo...). Por ejemplo, ciudades como vértices y el tiempo de viaje como peso de cada arista. Las representaciones anteriores se adaptan fácilmente para guardar ese valor.
Operaciones básicas sobre un grafo G
adyacentes(G, x, y): ¿hay arista entrexey? (booleano).vecinos(G, x): lista de vecinos dex.agregar_vertice/remover_vertice.agregar_arista/remover_arista.
python
class Grafo: def __init__(self, lista_adyacencia=None): self.lista_adyacencia = lista_adyacencia or dict() def adyacentes(self, x, y): return y in self.lista_adyacencia[x] def vecinos(self, x):