{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "

\n", "IIC2233 Apunte Programación Avanzada
\n", "© 2016 Ivania Donoso - Antonio Ossa.\n", "
\n", " Modificado 2026-1 por Equipo Docente IIC2233\n", "

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Tabla de contenidos\n", "\n", "1. [Grafos](#Grafos)\n", "2. [Representación](#Representación)\n", " 1. [Representación con nodos](#Representación-con-nodos)\n", " 2. [Listas de adyacencia](#Listas-de-adyacencia)\n", " 3. [Matriz de adyacencia](#Matriz-de-adyacencia)\n", "3. [Pesos en aristas](#Pesos-en-aristas)\n", "4. [Operaciones básicas](#Operaciones-basicas-en-grafos)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Grafos\n", "\n", "Un grafo es un conjunto no vacío compuesto por **nodos** y por las **relaciones entre estos nodos**.\n", "En teoría de grafos, a los nodos se les llama **vértices**; y a las relaciones entre ellos, **aristas**. \n", "\n", "Los grafos pueden ser **dirigidos** o **no dirigidos**. Que un grafo sea dirigido significa que las relaciones entre los nodos **sí** tienen una orientación o dirección: si el nodo $A$ está relacionado con el nodo $B$, esto **no** significa que el nodo $B$ está relacionado con el nodo $A$ (siendo una relación no simétrica). En cambio, en los grafos no digiridos, las relaciones son simétricas: el nodo $A$ está relacionado con el nodo $B$, si y sólo si el nodo $B$ está relacionado con el nodo $A$.\n", "\n", "![ejemplo](imgs/grafos.png)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "En el ejemplo, notamos que el primer grafo las relaciones conectan los distintos nodos y no hay diferenciación de orientación. Mientras que en el segundo, tienen dirección. El nodo 1 se relaciona con el 2, pero el 2 no se relaciona con el 1. En cambio, los nodos 2 y 3 sí se relacionan entre sí, en ambas direcciones.\n", "\n", "Un caso de grafo no dirigido es la amistad en Facebook, si aceptas la amistad de una persona, ambos serán amigos/as. En cambio, seguir a alguien en Instagram es dirigido, una persona A puede seguir a una persona B, pero no eso no implica que B siga a A.\n", "\n", "Los grafos pueden ser vistos como una generalización de las dos estructuras que estudiamos previamente: **listas ligadas** y **árboles**. Ambos son casos de grafos con distintas reglas sobre su forma: linealidad (listas ligadas) y jerarquía (árboles). En grafos, en cambio, no hay condiciones sobre cómo se relacionan los vértices. En este curso, no estudiaremos [**teoría de grafos**](https://es.wikipedia.org/wiki/Teoría_de_grafos). Sólo nos limitaremos a estudiar las estructuras de datos que se usan para representarlos y operar con ellos. \n", "\n", "## Representación\n", "\n", "Existen múltiples formas para representar grafos. En este curso examinaremos tres de ellas: representación con nodos, listas de adyacencia y matrices de adyacencia. \n", "\n", "### Representación con nodos\n", "\n", "Esta es la forma más natural de representar un grafo: se define la clase nodo (`Nodo`), que tiene una lista de nodos a los cuales está relacionado directamente. En un grafo no dirigido, una conexión `(a, b)` será guardada dos veces: primero, en la lista de vecinos en `a` y segundo, en la lista de vecinos de `b`." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "# Nodo de un grafo\n", "class Nodo:\n", "\n", " # Un nodo está compuesto por el valor que almacena y una lista de sus nodos vecinos\n", " def __init__(self, valor):\n", " self.valor = valor\n", " self.vecinos = []\n", "\n", " def agregar_vecino(self, nodo):\n", " self.vecinos.append(nodo)\n", "\n", " def __repr__(self):\n", " texto = f\"[{self.valor}]\"\n", " if len(self.vecinos) > 0:\n", " textos_vecinos = [f\"[{vecino.valor}]\" for vecino in self.vecinos]\n", " texto += \" -> \" + \", \".join(textos_vecinos)\n", " return texto" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Vamos a crear el grafo _dirigido_ de la imagen de arriba:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "nodo_1 = Nodo(1)\n", "nodo_2 = Nodo(2)\n", "nodo_3 = Nodo(3)\n", "nodo_4 = Nodo(4)\n", "nodo_5 = Nodo(5)\n", "\n", "nodo_1.agregar_vecino(nodo_2)\n", "nodo_2.agregar_vecino(nodo_3) \n", "nodo_3.agregar_vecino(nodo_2) \n", "nodo_3.agregar_vecino(nodo_4)\n", "nodo_3.agregar_vecino(nodo_5) \n", "nodo_4.agregar_vecino(nodo_5)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Este es el resultado, tal y como esperábamos." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1] -> [2]\n", "[2] -> [3]\n", "[3] -> [2], [4], [5]\n", "[4] -> [5]\n", "[5]\n" ] } ], "source": [ "print(nodo_1)\n", "print(nodo_2)\n", "print(nodo_3)\n", "print(nodo_4)\n", "print(nodo_5)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Listas de adyacencia\n", "\n", "En esta representación todos los vértices se guardan en una estructura, y a su vez para cada uno de ellos se guarda una lista con los vértices con los que está relacionados. Los grafos de la imagen de arriba se representarían como:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "# Aquí usamos diccionarios con llave: int y valor: list porque ofrece más facilidad de búsqueda.\n", "# Cada llave del diccionario es el valor de un vértice, y el valor asociado es la lista de vértices con conexión.\n", "\n", "grafo_no_dirigido = {\n", " 1: [2], \n", " 2: [1, 3], \n", " 3: [2, 4, 5], \n", " 4: [3, 5], \n", " 5: [3, 4]\n", "}\n", "\n", "grafo_dirigido = {\n", " 1: [2], \n", " 2: [3], \n", " 3: [2, 4, 5], \n", " 4: [5], \n", " 5: []\n", "}" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Lista de vértices: [1, 2, 3, 4, 5]\n", "Vecinos del vértices 3: [2, 4, 5]\n" ] } ], "source": [ "# Podemos obtener los vértices del grafo como las llaves del diccionario\n", "print(\"Lista de vértices:\", list(grafo_no_dirigido.keys()))\n", "\n", "# ¿Quiénes son los vecinos del vértice 3 en el grafo no dirigido?\n", "print(\"Vecinos del vértices 3:\", grafo_no_dirigido[3])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Una ventaja de la representación con lista de adyacencia es que, dado un grafo, es fácil encontrar un vértice en particular ya que usamos la llave del diccionario, y desde él también es fácil obtener la lista de vecinos." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Matriz de adyacencia\n", "\n", "Son matrices de dos dimensiones, de `NxN` (`N` siendo el número de vértices o nodos), donde las filas representan los vértices de origen y las columnas los vértices de llegada. Cada celda contiene un `1` o un `0`: si hay una arista que conecta al vértice de la fila con el vértice de de la columna, entonces contiene un `1`, en caso contrario, un `0`. Notar que esta representación solo contiene información sobre las conexiones, se debe realizar de forma aparte la asociación entre los índices de esta matriz y los valores que tiene cada vértice. En Python las podemos representar con listas de listas, o generarlas utilizando bibliotecas especializadas para manejo de matrices como [`numpy`](http://www.numpy.org/), el cual veremos esta semana.\n", "\n", "En un grafo no dirigido, la matriz será simétrica. En uno dirigido, no será necesariamente simétrica." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "grafo_no_dirigido = [[0, 1, 0, 0, 0], \n", " [1, 0, 1, 0, 0],\n", " [0, 1, 0, 1, 1], \n", " [0, 0, 1, 0, 1], \n", " [0, 0, 1, 1, 0]]\n", "\n", "grafo_dirigido = [[0, 1, 0, 0, 0], \n", " [0, 0, 1, 0, 0], \n", " [0, 1, 0, 1, 1], \n", " [0, 0, 0, 0, 1], \n", " [0, 0, 0, 0, 0]]" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0, 1, 0, 0, 0]\n", "[1, 0, 1, 0, 0]\n", "[0, 1, 0, 1, 1]\n", "[0, 0, 1, 0, 1]\n", "[0, 0, 1, 1, 0]\n" ] } ], "source": [ "for fila in grafo_no_dirigido:\n", " print(fila)" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0, 1, 0, 0, 0]\n", "[0, 0, 1, 0, 0]\n", "[0, 1, 0, 1, 1]\n", "[0, 0, 0, 0, 1]\n", "[0, 0, 0, 0, 0]\n" ] } ], "source": [ "for fila in grafo_dirigido:\n", " print(fila)" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# ¿Están relacionados en el grafo dirigido el vértice 4 y 1?\n", "1 == grafo_dirigido[4 - 1][1 - 1] # Se le resta 1 porque los índices van desde 0 hasta N -1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Esta representación es fácil de leer porque podemos saber fácilmente si hay una arista entre dos vértices. Basta con ver si hay un uno en la celda correspondiente.\n", "\n", "Su desventaja es que en grafos grandes, la representación ocupa mucho espacio. Para representar un grafo de $N$ nodos, se necesitan almacenar $N\\times N$ valores, o utilizar alguna estructura más eficiente como las _sparse matrix_. Más aún, si el grafo tiene pocas conexiones, la mayoría de las posiciones será $0$. La representación con lista de adyacencia es bastante más económica en espacio cuando no hay muchas aristas." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "## Pesos en aristas\n", "\n", "Algunas representaciones de grafos permiten asignarle pesos o valores a las aristas de un grafo. Esto permite diferenciar aún más las aristas. En la siguiente figura, se le asocia un valor numérico entero a cada arista:\n", "\n", "![ejemplo](imgs/grafos_y_pesos.png)\n", "\n", "El asignar valores a las aristas nos permite modelar situaciones más reales. Por ejemplo, modelar rutas entre ciudades. Cada ciudad puede ser un vértice en un grafo, y las aristas determinan si hay un camino directo entre dos ciudades. El peso de cada arista podría representar el tiempo que toma ir de una ciudad a otra. Es más, esos caminos tienen caracteristicas: distancia, condiciones climaticas, estado del camino, etc... Luego, las aristas podrían contener estos atributos que describen como se conectan distintas ciudades.\n", "\n", "Las representaciones vistas anteriormente solo incluyen una forma de modelar la presencia de una arista entre dos vértices, pero se pueden modificar fácilmente para incluir un valor asociado a cada arista.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Operaciones basicas en grafos\n", "\n", "Las operaciones básicas que se implementan para un grafo `G` son:\n", "\n", "* **`adyacentes(G, x, y)`**. Indica si existe una arista entre `x` e `y`. Retorna un booleano.\n", "\n", "* **`vecinos(G, x)`**. Entrega una lista con todos los vértices `y` tales que existe una arista entre `x` e `y`. Retorna una lista de nodos.\n", "\n", "* **`agregar_vertice(G, x)`**. Agrega el vértice `x` al grafo.\n", "\n", "* **`remover_vertice(G, x)`**. Elimina el vértice `x` del grafo.\n", "\n", "* **`agregar_arista(G, x, y)`**. Agrega una arista entre los vértices `x` e `y`.\n", "\n", "* **`remover_arista(G, x, y)`**. Elimia la arista entre `x` e `y`." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Además de las operaciones mencionadas anteriormente, se pueden implementar funciones para obtener y fijar valores de vértices o aristas en el grafo. Estas no son consideradas necesariamente operaciones básicas de grafos, ya que su implementación depende fuertemente de la modelación y estructura utilizada. Utilizaremos las operaciones listadas como las básicas para el siguiente ejemplo." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Ejemplo: grafo de amistades\n", "\n", "Supongamos que quieres representar a tus amigos como un grafo. **Cada nodo sería una persona**, y cada vez que un nodo $A$ se conecte con un nodo $B$ significa que **$A$ considera que $B$ es su amigo**. No siempre esta relación es simétrica; es decir, no siempre nuestros amigos creen que somos sus amigos. De hecho, cerca de la mitad de las personas que consideramos nuestros amigos no nos consideran amigos suyos ([comprobado cientificamente](http://www.nytimes.com/2016/08/07/opinion/sunday/do-your-friends-actually-like-you.html)). Por lo tanto el grafo que tendremos que representar es un **grafo dirigido**.\n", "\n", "Partamos con la clase `Persona`." ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": [ "class Persona:\n", "\n", " def __init__(self, nombre, edad):\n", " self.nombre = nombre\n", " self.edad = edad\n", "\n", " def __repr__(self):\n", " return self.nombre" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Como dijimos, cada nodo es una persona. Para esto tenemos dos posibilidades: cada nodo tiene como valor a un objeto del tipo `Persona`, o cada Persona es un nodo en el grafo. Para este ejemplo, haremos lo primero. Crearemos una clase `Nodo` cuyo valor sea del tipo `Persona`. Esto simplemente es una decisión de modelación, donde `Nodo` es la clase para encapsular posibles valores, e independizarlo del tipo del valor que contiene, que en este caso son de la clase `Persona`.\n", "\n", "Si, por ejemplo, la entidad `Persona` no tiene muchas funcionalidades y simplemente funciona como nodo, podría modelarse de la segunda forma." ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [], "source": [ "# En este modelamiento, cada nodo del grafo posee un valor.\n", "# Esto permite modelar cualquier nodo de un grafo.\n", "\n", "# Para nuestro ejemplo, el valor será un objeto de clase Persona.\n", "class Nodo:\n", "\n", " def __init__(self, valor):\n", " self.valor = valor\n", "\n", " def __repr__(self):\n", " return repr(self.valor)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ahora definimos la clase `Grafo`, representado como **listas de adyacencia**, sobre la cual realizaremos nuestras operaciones." ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [], "source": [ "class Grafo:\n", " # Permitimos que el grafo se construya a partir de una lista de adyacencia existente,\n", " # o bien que parte con una lista de adyacencia vacío (un diccionario vacío)\n", " def __init__(self, lista_adyacencia=None):\n", " self.lista_adyacencia = lista_adyacencia or dict()\n", "\n", " # Encontrar si 'x' e 'y' están conectados se puede lograr buscando 'y' en la lista de adyacencia de 'x',\n", " def adyacentes(self, x, y):\n", " return y in self.lista_adyacencia[x]\n", "\n", " # Para encontrar la lista de vecinos de un nodo 'x', simplemente accedemos a su lista de adyacencia\n", " def vecinos(self, x):\n", " return self.lista_adyacencia[x]\n", "\n", " # Para agregar un vértice 'x' al grafo, agregamos una llave más al diccionario\n", " # que mantiene la listas de adyacencia.\n", " # Como la lista de adyacencia de 'x' está inicialmente vacía, la inicializamos con un conjunto vacío\n", " # También podía haber sido una lista vacía\n", " def agregar_vertice(self, x):\n", " self.lista_adyacencia[x] = set()\n", "\n", " # Eliminar un vertice requiere un poco más de trabajo porque también hay que eliminar su conexiones\n", " # (aristas) con el resto del grafo.\n", " # El método 'pop(x,V)' de un diccionario elimina la entrada que tiene llave 'x'.\n", " # Si la llave 'x' no existe en el diccionario, retorna el valor por defecto 'V'\n", " # Luego de eliminar la entrada con llave 'x', se debe recorrer el grafo y eliminar todos las entradas\n", " # que se refieran a 'x'\n", " def remover_vertice(self, x):\n", " self.lista_adyacencia.pop(x, None)\n", " for k, v in self.lista_adyacencia.items():\n", " if x in v:\n", " v.remove(x)\n", "\n", " # Para agregar una arista entre 'x' e 'y', debemos ir a la lista de adyacencia de 'x'\n", " # y agregar 'y' al conjunto\n", " def agregar_arista(self, x, y):\n", " if x in self.lista_adyacencia:\n", " self.lista_adyacencia[x].add(y)\n", "\n", " # Eliminar unar arista entre 'x' e 'y' requiere buscar la entrada de 'y' en a lista de adyacencia de 'x'\n", " def remover_arista(self, x, y):\n", " vecinos_x = self.lista_adyacencia.get(x, set())\n", " if y in vecinos_x:\n", " vecinos_x.remove(y)\n", "\n", " def __repr__(self):\n", " texto_nodos = []\n", " for nodo, vecinos in self.lista_adyacencia.items():\n", " texto_nodos.append(f\"Amigos de {nodo}: {vecinos}.\")\n", " return \"\\n\".join(texto_nodos)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Veamos cómo se llevan las siguientes personas. \n", "(*Los nombres y amistades vertidas en éste código son completamente ficticios. Cualquier parecido con personas reales es pura coincidencia.*)" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Amigos de Coco: {Tomás, Anya, Thor, Bon, Kira, Luna}.\n", "Amigos de Thor: {Tomás, Kira, Anya}.\n", "Amigos de Luna: {Anya, Thor, Bon}.\n", "Amigos de Bon: {Luna, Anya, Tomás}.\n", "Amigos de Kira: {Luna, Anya, Thor, Bon}.\n", "Amigos de Anya: {Luna, Kira, Thor, Bon}." ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Creamos a nuestras personas y los guardamos en nodos.\n", "coco = Nodo(Persona(\"Coco\", 15))\n", "thor = Nodo(Persona(\"Thor\", 20))\n", "luna = Nodo(Persona(\"Luna\", 21))\n", "kira = Nodo(Persona(\"Kira\", 20))\n", "bon = Nodo(Persona(\"Bon\", 20))\n", "tomas = Nodo(Persona(\"Tomás\", 10))\n", "anya = Nodo(Persona(\"Anya\", 22))\n", "\n", "# Definimos las amistades.\n", "amistades = {\n", " coco: set([thor, luna, kira, bon, tomas, anya]),\n", " thor: set([kira, tomas, anya]),\n", " luna: set([thor, bon, anya]),\n", " bon: set([luna, tomas, anya]),\n", " kira: set([thor, luna, bon, anya]),\n", " anya: set([thor, luna, kira, bon])\n", "}\n", "\n", "grafo = Grafo(amistades)\n", "grafo" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Amigos de Tomás: set()\n", "Amigos de Tomás: {Luna, Coco}\n" ] } ], "source": [ "# ¡Rayos! Nos olvidamos de una persona...\n", "# Siempre nos olvidamos de Tomás :(\n", "grafo.agregar_vertice(tomas)\n", "print(f\"Amigos de {tomas}: {grafo.vecinos(tomas)}\")\n", "\n", "# Tomás dice que tiene algunos amigos.\n", "grafo.agregar_arista(tomas, luna)\n", "grafo.agregar_arista(tomas, coco)\n", "print(f\"Amigos de {tomas}: {grafo.vecinos(tomas)}\")\n", "\n", "# Y Jüne dice que Tomás es su amigo.\n", "grafo.agregar_arista(bon, tomas)" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Amigos de Coco: {Tomás, Anya, Bon, Kira, Luna}.\n", "Amigos de Luna: {Anya, Bon}.\n", "Amigos de Bon: {Luna, Anya, Tomás}.\n", "Amigos de Kira: {Luna, Anya, Bon}.\n", "Amigos de Anya: {Luna, Kira, Bon}.\n", "Amigos de Tomás: {Luna, Coco}." ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# A Thor le cae mal Tomás, así que renuncia.\n", "grafo.remover_vertice(thor)\n", "grafo" ] } ], "metadata": { "kernelspec": { "display_name": "3.11.11", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.11.11" } }, "nbformat": 4, "nbformat_minor": 4 }