{ "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. [Cómo recorrer o buscar en un grafo](#Cómo-recorrer-o-buscar-en-un-grafo)\n", " 1. [*BFS: Breadth-first search*](#BFS:-Breadth-first-search)\n", " 2. [*DFS: Depth-first search*](#DFS:-Depth-first-search)\n", " 1. [DFS iterativo](#DFS-iterativo)\n", " 2. [DFS recursivo](#DFS-recursivo)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Cómo recorrer o buscar en un grafo\n", "\n", "Podemos recorrer un grafo usando los mismos métodos que utilizamos para árboles (BFS y DFS). Pero debemos tener cuidado en la implementación.\n", "\n", "Vamos a realizar estos recorridos sobre el grafo de amistades que ya hemos utilizado." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Amigos de Coco: {Kira, Luna, Bon, Tomás, Anya, Thor}.\n", "Amigos de Thor: {Kira, Anya, Tomás}.\n", "Amigos de Luna: {Thor, Anya, Bon}.\n", "Amigos de Bon: {Tomás, Anya, Luna}.\n", "Amigos de Kira: {Thor, Anya, Bon, Luna}.\n", "Amigos de Anya: {Thor, Bon, Kira, Luna}.\n", "Amigos de Tomás: {Bon, Coco}." ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Utilizaremos estas definiciones para Persona, Nodo y Grafo, que ya habíamos revisado anteriormente.\n", "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\n", "\n", "\n", "class Nodo:\n", "\n", " def __init__(self, valor):\n", " self.valor = valor\n", "\n", " def __repr__(self):\n", " return repr(self.valor)\n", "\n", "\n", "class Grafo:\n", "\n", " def __init__(self, lista_adyacencia=None):\n", " self.lista_adyacencia = lista_adyacencia or dict()\n", "\n", " def adyacentes(self, x, y):\n", " return y in self.lista_adyacencia[x]\n", "\n", " def vecinos(self, x):\n", " return self.lista_adyacencia[x]\n", "\n", " def agregar_vertice(self, x):\n", " self.lista_adyacencia[x] = set()\n", "\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", " def agregar_arista(self, x, y):\n", " if x in self.lista_adyacencia:\n", " self.lista_adyacencia[x].add(y)\n", "\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)\n", "\n", "\n", "# Creamos varios nodos que representan a las personas y \n", "# construimos un grafo para modelar sus relaciones de amistad.\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", " tomas: set([bon, coco])\n", "}\n", "\n", "grafo = Grafo(amistades)\n", "grafo" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ahora intentaremos aplicar el mismo algoritmo de BFS que usamos para un árbol. Agregaremos un argumento `limite` para limitar la cantidad de nodos que visitamos:" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [], "source": [ "from collections import deque\n", "\n", "\n", "def bfs(grafo, inicio, limite=20):\n", " # La cola de siempre, comienza desde el nodo inicio.\n", " cola = deque([inicio])\n", "\n", " # Mientras queden vertices por visitar y no nos pasemos del limite de navegación\n", " while len(cola) > 0 and limite > 0:\n", " # Obtenemos de la cola el próximo vertice\n", " vertice = cola.popleft()\n", " print(vertice)\n", " # Agregamos los vecinos al stack\n", " for vecino in grafo[vertice]:\n", " cola.append(vecino)\n", " # Visitamos un nodo, bajamos el límite en 1\n", " limite -= 1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ahora intentemos recorrer el grafo de amistades anterior, partiendo por Bon:" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Bon\n", "Tomás\n", "Anya\n", "Luna\n", "Bon\n", "Coco\n", "Thor\n", "Bon\n", "Kira\n", "Luna\n", "Thor\n", "Anya\n", "Bon\n", "Tomás\n", "Anya\n", "Luna\n", "Kira\n", "Luna\n", "Bon\n", "Tomás\n" ] } ], "source": [ "bfs(amistades, bon)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Notamos rápidamente que la salida del programa repite varios nombres. Incluso si aumentamos el valor de `limite`, el problema persiste. ¿Por qué ocurre esto?\n", "\n", "Al observar las amistades, descubrimos que existen **ciclos** dentro del grafo: secuencias de personas conectadas que eventualmente regresan al punto de partida. Por ejemplo, Bon y Luna son amigos entre sí, y además Tomás es amigo de Coco, quien es amiga de Luna, que a su vez es amiga de Bon, quien finalmente vuelve a tener de amigo a Tomás. Al recorrer estos vértices, el algoritmo termina visitando nuevamente nodos que ya había procesado, quedando atrapado en un ciclo.\n", "\n", "Esto no sucede en los **árboles**, porque su estructura garantiza que existe **una única ruta** para llegar a cada vértice, siempre a través de su nodo padre. Por lo tanto, en un árbol nunca se visita dos veces el mismo vértice con el algoritmo anterior.\n", "\n", "En cambio, en un **grafo general** sí pueden existir ciclos, por lo que es fundamental **registrar qué vértices ya han sido visitados**. De lo contrario, el recorrido podría volverse infinito y el programa nunca terminaría. En el ejemplo anterior, si no hubiésemos establecido un límite, el proceso habría continuado indefinidamente.\n", "\n", "A continuación, veremos las implementaciones de los algoritmos **BFS** y **DFS**, que incluyen este control para evitar recorrer dos veces el mismo vértice." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## *BFS: Breadth-first search*\n", "\n", "BFS recorre exhaustivamente el grafo, dado un punto de partida. Por lo tanto, si un nodo no fue visitado en el recorrido, significa que **no es alcanzable** desde ese punto de partida. \n", "\n", "BFS utiliza una **cola** para mantener el registro de los nodos que debe visitar. Inicialmente el único nodo en la cola es el nodo inicial. Una vez que se extrae un nodo de la cola y se visita, se agregan todos sus vecinos a la cola. Esto provoca que, luego de visitar el nodo inicial, se visitan todos los nodos que están a una arista del inicial; luego se visitan todos los que están a dos aristas del inicial; luego los que están a tres aristas del inicial, y así hasta haber visitado todos los nodos.\n", "\n", "Este modo de recorrer hace que cada vez visitamos todos los nodos que están a cierta \"distancia\" del nodo inicial antes de pasar a la distancia siguiente. Por este recorrido se llama **recorrido en amplitud (_breadth_)**\n", "\n", "BFS es práctico cuando se quiere encontrar **la cantidad mínima de aristas a recorrer** para llegar desde un nodo a otro. Esto puede considerarse equivalente a encontrar el \"camino más corto\" entre dos nodos cuando todos las aristas poseen en el mismo peso. En el caso más general, cuando cada arista puede tener un peso distinto, el criterio de búsqueda de BFS ya no es suficiente y hay otros algoritmos que permiten obtener el camino más corto.\n" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [], "source": [ "from collections import deque\n", "\n", "\n", "def bfs(grafo, inicio):\n", " # Vamos a mantener una lista con los nodos visitados.\n", " visitados = []\n", " # La cola de siempre, comienza desde el nodo inicio.\n", " queue = deque([inicio])\n", "\n", " while len(queue) > 0:\n", " # Elegimos el siguiente nodo a visitar de la cola\n", " vertice = queue.popleft()\n", " # Detalle clave: si ya visitamos el nodo, no hacemos nada!\n", " if vertice in visitados:\n", " continue\n", "\n", " # Lo visitamos\n", " print(vertice)\n", " visitados.append(vertice)\n", " # Agregamos los vecinos a la cola si es que no han sido visitados.\n", " for vecino in grafo[vertice]:\n", " if vecino not in visitados:\n", " queue.append(vecino)\n", " return visitados" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Bon\n", "Tomás\n", "Anya\n", "Luna\n", "Coco\n", "Thor\n", "Kira\n" ] }, { "data": { "text/plain": [ "[Bon, Tomás, Anya, Luna, Coco, Thor, Kira]" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "bfs(amistades, bon)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Notamos que (1) el algoritmo termina gracias a que mantenemos un registro en `visitados` de todos los nodos revisados y (2) que obtenemos todas las personas como resultado, ya que todas son alcanzables desde alguna otra persona (grafo conexo). \n", "\n", "Pero si cambiamos un poco el grafo, dónde no todos los nodos son alcanzables desde otros nodos, solo obtenemos algunos:" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [], "source": [ "grafo = {\n", " 'A': ['B', 'C'],\n", " 'B': ['D', 'A'],\n", " 'C': ['D'],\n", " 'D': ['B'],\n", " 'E': ['F'],\n", " 'F': ['E'],\n", " 'G': ['A', 'F'],\n", "}" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "A\n", "B\n", "C\n", "D\n", "Nodos alcanzables desde A: ['A', 'B', 'C', 'D']\n" ] } ], "source": [ "print(f\"Nodos alcanzables desde A: {bfs(grafo, 'A')}\")" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "E\n", "F\n", "Nodos alcanzables desde E: ['E', 'F']\n" ] } ], "source": [ "print(f\"Nodos alcanzables desde E: {bfs(grafo, 'E')}\")" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "G\n", "A\n", "F\n", "B\n", "C\n", "E\n", "D\n", "Nodos alcanzables desde G: ['G', 'A', 'F', 'B', 'C', 'E', 'D']\n" ] } ], "source": [ "print(f\"Nodos alcanzables desde G: {bfs(grafo, 'G')}\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Haz el ejercicio de dibujar el grafo anterior, y ve cómo el algoritmo va recorriendo qué nodos. Como nuestra implementación usa una lista para guardar a los nodos visitados, se mantiene el orden en que fueron agregados. Revisa por qué tiene ese orden los nodos alcanzables de cada resultado." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## *DFS: Depth-first search*\n", "\n", "Al igual que BFS, el algoritmo DFS recorre exhaustivamente el grafo, dado un punto de partida. Si un nodo no fue visitado en el recorrido, significa que **no es alcanzable** desde ese punto de partida.\n", "\n", "La diferencia con BFS es el orden en que se recorren los nodos. BFS realiza una **búsqueda por amplitud** (o \"por nivel\"), de manera que primero recorrerá todos los nodos que están a una arista del inicial, después todos los que están a dos aristas del inicial, luego a tres aristas, y así hasta recorrerlos todos.\n", "\n", "DFS explora **en profundidad (_depth_)** cada uno de los vecinos de un nodo. Esto significa que a partir del nodo inicial elige uno de sus vecinos y trata de llegar lo más lejos posible del nodo inicial (\"desciende por una rama\"); una vez que ha llegado lo más lejos posible, se devuelve e intenta otro camino. De esta manera el algoritmo explora cada \"rama\" completa del grafo antes de probar otra rama.\n", "\n", "DFS puede implementarse de manera muy similar a BFS pero cambiando la estructura en que se almacenan los nodos a visitar usando un **_stack_** en lugar de una cola.\n", "\n", "DFS también posee una implementación recursiva muy natural. A continuación presentamos ambas implementaciones." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### DFS iterativo\n", "\n", "La implementación iterativa de DFS es muy similar a la de BFS, pero DFS utiliza un _stack_ para mantener el registro de los nodos por visitar, mientras que BFS utiliza una cola. Esta diferencia provoca un cambio en el comportamiento del recorrido." ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [], "source": [ "def dfs(grafo, inicio):\n", " # Vamos a mantener un set con los nodos visitados.\n", " visitados = set()\n", "\n", " # El stack de siempre, comienza desde el nodo inicio.\n", " stack = [inicio]\n", "\n", " while len(stack) > 0:\n", " vertice = stack.pop()\n", " # Detalle clave: si ya visitamos el nodo, ¡no hacemos nada!\n", " if vertice in visitados:\n", " continue\n", "\n", " # Lo visitamos\n", " print(vertice)\n", " visitados.add(vertice)\n", "\n", " # Agregamos los vecinos al stack si es que no han sido visitados.\n", " for vecino in grafo[vertice]:\n", " if vecino not in visitados:\n", " stack.append(vecino)\n", "\n", " return list(visitados)" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Bon\n", "Luna\n", "Anya\n", "Kira\n", "Thor\n", "Tomás\n", "Coco\n" ] }, { "data": { "text/plain": [ "[Kira, Luna, Bon, Anya, Tomás, Coco, Thor]" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "dfs(amistades, bon)" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "A\n", "C\n", "D\n", "B\n", "Nodos alcanzables desde A: ['A', 'B', 'D', 'C']\n" ] } ], "source": [ "print(f\"Nodos alcanzables desde A: {dfs(grafo, 'A')}\")" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "E\n", "F\n", "Nodos alcanzables desde E: ['F', 'E']\n" ] } ], "source": [ "print(f\"Nodos alcanzables desde E: {dfs(grafo, 'E')}\")" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "G\n", "F\n", "E\n", "A\n", "C\n", "D\n", "B\n", "Nodos alcanzables desde G: ['F', 'B', 'A', 'D', 'E', 'C', 'G']\n" ] } ], "source": [ "print(f\"Nodos alcanzables desde G: {dfs(grafo, 'G')}\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Nota que los resultados (como conjuntos de nodos) son iguales que en BFS, pero el orden es lo que cambia. Revisa en este caso el por qué aparecen en el orden en que imprimen." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### DFS recursivo\n", "\n", "La versión recursiva recorre cada vertice, y se vuelve a llamar recursivamente con cada uno de los vecinos de ese vértice. También se hace necesario maetener en cada llamado una lista con los vértices ya visitados para evitar procesar más de una vez cada vértice." ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [], "source": [ "# Vamos a mantener como parámetro un set con los nodos visitados.\n", "def dfs_recursivo(grafo, vertice, visitados=None):\n", " visitados = visitados or set()\n", "\n", " # Lo visitamos\n", " print(vertice)\n", " visitados.add(vertice)\n", "\n", " for vecino in grafo[vertice]:\n", " # Detalle clave: si ya visitamos el nodo, ¡no hacemos nada!\n", " if vecino not in visitados:\n", " dfs_recursivo(grafo, vecino, visitados)\n", "\n", " return list(visitados)" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Bon\n", "Tomás\n", "Coco\n", "Kira\n", "Thor\n", "Anya\n", "Luna\n" ] }, { "data": { "text/plain": [ "[Kira, Luna, Bon, Tomás, Anya, Coco, Thor]" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "dfs_recursivo(amistades, bon)" ] } ], "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 }