PDF de programación - Algoritmos con Python - Grafos

Algoritmos con Python

Grafos

2 de marzo de 2021

Índice

1 Codificación en Python

2 Gráficos implícitos

2.1 Ejemplo: Rush Hour

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Búsqueda en profundidad: DFS

3.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 Detalles de implementacion . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5 Implementación mejorada . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6 El caso de una cuadrícula . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 Búsqueda en amplitud primero: BFS

4.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Observación clave . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Algoritmo en tiempo lineal O(|V| + |E|)
. . . . . . . . . . . . . . . . . . .
4.4 Detalles de implementacion . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5 Ejemplo: Prime Path . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

4
4

6
6
6
6
6
6
7

8
8
8
8
8
9

5 Componentes conectados

10
5.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5.2 Algoritmo por búsqueda en profundidad . . . . . . . . . . . . . . . . . . . . 10
5.3 Aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5.4 Algoritmo con la estructura Union-Find . . . . . . . . . . . . . . . . . . . . . 12
5.5 Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.6 Aplicación a la desconexión de un gráfico . . . . . . . . . . . . . . . . . . . . 12

6 Componentes biconectados

14
6.1 Aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.2 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.3 Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
6.4 Detalles de la búsqueda en profundidad . . . . . . . . . . . . . . . . . . . . 15
6.5 Determinación del tipo de arco . . . . . . . . . . . . . . . . . . . . . . . . . 16
6.6 Observación clave . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6.7 Detalles de implementacion . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

7 Orden topológico

20
7.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
7.2 Aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
7.3 Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
7.4 Algoritmo con un recorrido DFS . . . . . . . . . . . . . . . . . . . . . . . . . 21
7.5 Algoritmo codicioso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

I

7.6 Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
7.7 Ejemplo: todos los discos considerados (Enlace)
. . . . . . . . . . . . . . . . 22

8 Componentes fuertemente conectados

24
8.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
8.2 Observación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
8.3 Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
8.4 Algoritmo de Tarjan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
8.5 Detalles de implementacion . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
8.6 Versión iterativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
8.7 Algoritmo de Kosaraju . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
8.8 Detalles de implementacion . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

9 2-SAT

30
9.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
9.2 Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
9.3 Modelado mediante un gráfico dirigido . . . . . . . . . . . . . . . . . . . . . 30
9.4 Observación clave . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
9.5 Detalles de implementacion . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

II

Introducción

Un grafo es un objeto combinatorio compuesto por un conjunto de vértices V (también
conocidos como nodos) y un conjunto de aristas E. Las aristas corresponden a pares de
vértices, que generalmente son distintos, y sin una noción de orden en el sentido donde
(u, v) y (v, u) denotan el mismo borde.

A veces, consideramos una variante, el grafo dirigido, donde los bordes tienen una orienta-
ción. En este caso, los bordes se conocen generalmente como arcos. El arco (u, v) tiene
origen u y destino v. La mayoría de los algoritmos descritos en este texto operan en grafos
dirigidos, pero se pueden aplicar a grafos no dirigidos reemplazando cada borde (u, v)
por dos arcos (u, v) y (v, u).

Los grafos pueden contener información adicional, como pesos o letras, en forma de eti-
quetas en los vértices o los bordes.

1

1. Codificación en Python

Una manera simple de codificar un grafo es identificar los n vértices por los números en-
teros de 0 a n - 1. Sin embargo, es común numerar los vértices comenzando desde 1
cuando se muestra un grafo o cuando se lee de un archivo de entrada. Por lo tanto, recuer-
de sumar o restar 1 de los índices al visualizar o leer un grafo.

Figura 1: Un grafo y sus posibles codificaciones

Los bordes se pueden representar esencialmente de dos maneras, por lista de adyacencia
o por matriz de adyacencia. Este último es a veces más simple de implementar pero re-
quiere más memoria: el grafo está representado por una matriz binaria E tal que E[u, v]
indica la existencia de un arco (u, v), ver Figura 1.

La representación por lista de adyacencia consiste en simbolizar el grafo por una lista de
listas G. Para un vértice u, G[u] es la lista de vecinos de u. Los vértices también se pueden
designar mediante un identificador textual, en cuyo caso G podría ser un diccionario cuyas
claves son cadenas y cuyos valores son las listas de vecinos. Por ejemplo, el triángulo
compuesto por tres vértices ’axel’, ’bill’ y ’carl’ estaría codificado por el siguiente
diccionario:

{’axel’: [’bill’, ’carl’], ’bill’: [’axel’, ’carl’], ’carl’: [’axel’, ’bill’]}

En un grafo dirigido, a veces necesitamos dos estructuras G_out, G_in, que contienen los
arcos que se originan y terminan en cada vértice. Sin embargo, en lugar de almacenar el
arco, almacenamos los puntos finales de los arcos. Por tanto, para cada vértice u, G_out[u]
contiene la lista de vértices v para cada arco saliente (u, v) y G_in[u] la lista de vértices
v para cada arco entrante (v, u).

Una forma sencilla de almacenar etiquetas en los vértices y los bordes es utilizar matrices
complementarias indexadas por los vértices o matrices indexadas por pares de vértices.
De esta manera, la estructura de la codificación del grafo G en sí no se ve afectada, y G
puede usarse sin modificación en las partes del código que no están relacionadas con las
etiquetas.

Ciertas implementaciones de algoritmos de grafos requieren que los vértices sean simple-
mente los números enteros entre 0 y n - 1, mientras que a veces los vértices necesitan

2

ser identificados por un nombre o por un objeto más complejo pero inmutable, como una
cadena o una n-tupla de enteros. Para proporcionar una interfaz entre estos fragmentos
de código, se puede escribir una pequeña clase, traduciendo entre el índice de un vértice
y el objeto complejo que representa. Dicha clase contendría un diccionario name2node que
relaciona el nombre de un vértice con su índice, y una matriz node2name que proporciona
la función inversa. Si G es una instancia de la clase Graph, entonces la expresión len(G)
debería devolver el número de sus vértices y G[u] la lista de adyacencia del vértice con
índice u. Entonces la clase se comporta exactamente como una lista de adyacencia, y
además permite agregar vértices y aristas usando los nombres de los vértices.

class Graph :

def _ _ i n i t _ _ ( s e l f ) :

s e l f . neighbors = [ ]
s e l f .name2node = {}
s e l f .node2name = [ ]
s e l f . weight = [ ]

def __len__ ( s e l f ) :

return len ( s e l f .node2name)

def __getitem__ ( self , v ) :

return s e l f . neighbors [v]

def add_node( self , name) :

assert name not in s e l f .name2node
s e l f .name2node[name] = len ( s e l f .name2node)
s e l f .node2name. append(name)
s e l f . neighbors . append ( [ ] )
s e l f . weight . append({})
return s e l f .name2node[name]

def add_edge( self , name_u, name_v, weight_uv=None) :

s e l f . add_arc (name_u, name_v, weight_uv )
s e l f . add_arc (name_v, name_u, weight_uv )

def add_arc ( self , name_u, name_v, weight_uv=None) :

u = s e l f .name2node[name_u]
v = s e l f .name2node[name_v]
s e l f . neighbors [u ] . append(v)
s e l f . weight [u ] [ v] = weight_uv

3

2. Gráficos implícitos

En ocasiones, el gráfico se da implícitamente, por ejemplo, en forma de cuadrícula, donde
los vértices son las celdas de la cuadrícula y los bordes corresponden a las celdas adyacen-
tes, como en un laberinto. Otro ejemplo de un gráfico dado implícitamente es con objetos
combinatorios, donde un arco corresponde a una modificación local.

2.1. Ejemplo: Rush Hour

Rush Hour es un rompecabezas disponible comercialmente. El tablero de juego es una
cuadrícula de 6 x 6, ver Figura 2. Los coches (de longitud 2) y camiones (de longitud 3)
se colocan en la cuadrícula, sin superponerse y sin salir del límite de la cuadrícula. Un
automóvil específico está marcado en un tono más oscuro, y el objetivo es que salga de
la cuadrícula a través de la apertura única en el límite. Para ello, es posible mover los
vehículos hacia adelante o hacia atrás.

La modelización con un grafo es sencilla. Los datos de cada uno de los k vehículos incluyen
una parte fija y una parte va