Contents

Recorridos sobre grafos

!wget -nc --no-cache -O init.py -q https://raw.githubusercontent.com/rramosp/introalgs.v1/main/content/init.py
import init; init.init(force_download=False);

Recorridos sobre grafos

Objetivo

Aprender las diferentes formas de recorrer un grafo y construir los algoritmos correspondientes.

## Preguntas básicas

  1. ¿En qué consiste el recorrido DFS sobre un grafo?

  2. ¿En qué consiste el recorrido BFS sobre un grafo?

Introducción

Al igual que en los árboles, los grafos son estructuras en las cuales una de las principales operaciones es el recorrido sobre ellas. Trataremos en este módulo las diferentes formas en que se recorren los árboles.

Recorrido DFS. Recibe este nombre porque son las iniciales de las palabras en inglés Depth First Search: búsqueda primero en profundidad. El recorrido DFS consiste en: estando ubicados en un vértice i cualquiera, determinar los vértices adyacentes, de esos vértices adyacentes elegir uno que no haya sido visitado y a partir de ahí iniciar nuevamente recorrido DFS. Observe que estamos planteando una definición recursiva para el recorrido.

Recorrido BFS. Recibe este nombre porque son las iniciales de las palabras en inglés Breadth First Search: búsqueda primero a lo ancho. Hay una diferencia sustancial entre este recorrido y el DFS: mientras que en el recorrido DFS no se visitan de una vez todos los adyacentes a un vértice dado, aquí hay que visitar primero todos los vértices adyacentes a un vértice dado antes de continuar el recorrido

Ejemplo de uso e implementación

usaremos colas para controlar y determinar un recorrido BFS o BFS. Observa el uso de deque en Python

from collections import deque
import numpy as np
x = np.random.randint(100, size=10)
print("int list  ", x)
queue = deque()
for i in x:
    queue.append(i)
print("pop       ", end=' ')
while len(queue)>0:
    print(queue.pop(), end=' ')

    
queue = deque()
for i in x:
    queue.append(i)
print("\npop left  ", end=' ')
while len(queue)>0:
    print(queue.popleft(), end=' ')

int list   [17  9 36 40 76 79 86 25 65 15]
pop        15 65 25 86 79 76 40 36 9 17 
pop left   17 9 36 40 76 79 86 25 65 15

Recorridos sobre un laberinto

Observa cómo implemnetamos un recorrido con obstáculos:

  • cómo describrimos el laberinto

  • cómo el laberinto es equivalente a un grafo

import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
%matplotlib inline

EMPTY, WALL, TARGET, USED = ".","X","T","o"
c  = pd.Series({"EMPTY": ".", "WALL":"X", "TARGET":"T", "USED":"o"})
ci = pd.Series({".": 0, "X": 255, "T":100, "o":200})

def plot_map(grid,p=[]):
    img = np.r_[[[ci[i] for i in j] for j in grid]]
    plt.imshow(img, alpha=.5)
    if(len(p)>0):
        for i in range(len(p)-1):
            plt.plot([p[i][1],p[i+1][1]],[p[i][0],p[i+1][0]], color="black", lw=4)    
        plt.title("path length = %d"%len(p))
        
    plt.xticks(list(range(img.shape[1])), list(range(img.shape[1])))
    plt.yticks(list(range(img.shape[0])), list(range(img.shape[0])))
    
def possible_moves(grid, y,x):
    moves = [ [y,x+1], [y-1,x], [y,x-1], [y+1,x]]
    
    moves = [(my,mx) for my,mx in moves if mx>=0 and mx<len(grid[0]) and \
                                           my>=0 and my<len(grid) and grid[my][mx]!=c.WALL]    
    return moves

grid = ["...XX",
        "....X",
        ".X..T"]

plot_map(grid)
../_images/NOTAS 09 - Recorridos sobre grafos_6_0.png

este laberinto es equivalente al siguiente grafo.

import networkx as nx
import itertools
def draw_graph(grid, path=None, node_size=900, font_color="white"):
    g = nx.Graph()
    g.add_nodes_from([(i,j) for i,j in itertools.product(list(range(len(grid))), list(range(len(grid[0])))) if grid[i][j]!="X"])
    for i,j in g.nodes:
        for ni,nj in possible_moves(grid, i,j):
            g.add_edge((i,j), (ni,nj))
            
    if path is None:
        c = "blue"
    else:
        c = [1 if i in p else 0 for i in g.nodes.keys()]
    nx.drawing.draw(g, with_labels=True, 
                    node_alpha=.2, node_color=c, 
                    node_size=node_size, font_color=font_color)

draw_graph(grid)
../_images/NOTAS 09 - Recorridos sobre grafos_9_0.png

preuba con distintos laberintos para construir tu intuición del grafo asociado

grid = [".....X",
        "XX...X",
        "...X..",
        ".XX..X",
        ".X...T"]

plot_map(grid)
../_images/NOTAS 09 - Recorridos sobre grafos_11_0.png 
draw_graph(grid)
../_images/NOTAS 09 - Recorridos sobre grafos_12_0.png

previous

Grafos

next

Algoritmos sobre grafos