Unidad 6:

Grafos y algoritmos asociados

Algoritmos y Estructuras de Datos

Contenido

Unidad 6 - Grafos y algoritmos asociados

Definición formal de grafo. Representaciones computacionales de grafos. Clasificaciones de grafos. Algoritmos de grafos: búsqueda, recorrido, ordenamiento topológico, algoritmo de Prim, algoritmo de Dijkstra, algoritmo de Warshall.

Objetivos

• Introducir los grafos: definiciones y clasificaciones
• Estudiar las formas de representación de grafos
• Estudiar algoritmos de recorrido y búsqueda en grafos
• Estudiar algoritmos asociados a grafos: Dijkstra, Prim, Warshall

Introducción

Introducción

Dado el mapa de Königsberg, con el río Pregel dividiendo el plano en cuatro regiones distintas, que están unidas a través de los siete puentes, ¿es posible dar un paseo comenzando desde cualquiera de estas regiones, pasando por todos los puentes, recorriendo solo una vez cada uno, y regresando al mismo punto de partida?

Introducción

Grafo de ciudades y rutas. Construcción de mapas y modelos

Introducción

Grafo de interacción gen - gen

​

Introducción

Grafos sociales y componentes fuertemente conectadas (CFC)

Métodos para detectar comunidades

Introducción

Grafos sociales y componentes fuertemente conectadas

Fuente: enlace a apartado 7.18 del libro

Introducción

Más ejemplos de elementos que pueden ser modelados con grafos.

1. Estructura química
2. Red Social
3. Circuito Eléctrico
4. Conexión de estaciones de tren subterráneo

​

​

Introducción

Modelado y simulación in silico del ciclo

de la metionina: una aproximación

mediante Redes de Petri

Términos, usos y definiciones

Vértice o Nodo: V (vertex)

Arcos: E (edge)

Ponderación

Ruta

Grado

Ciclo

Grafo acíclico dirigido

Términos, usos y definiciones

Según los arcos sean dirigidos o no.

Términos, usos y definiciones

Grafos G y su versión traspuesta G^T.

G

G^T

Términos, usos y definiciones

Grafo acíclico dirigido, GAD

​

(también pueden nombrarse como

grafos dirigidos acíclicos, GDA)

Definiciones de grafo

Grafo:

Sea un conjunto de vértices V y un conjunto de aristas (o arcos) E, un grafo G es una tupla G=(V, E) donde cada arista es, a su vez, una tupla e=(v,w) tal que v, w ∈ V y se dice que e va de v a w. Si el grafo es ponderado, puede añadirse un tercer componente al arco e para representar una ponderación: ejemplo e=(v,w,p)

Subgrafo:

Un subgrafo G_s del grafo G=(V, E) es otro grafo G_s=(V_s , E_s) tal que V_s y E_s son conjuntos de vértices y aristas, respectivamente y, además, V_s⊂ V y E_s⊂ E

Representaciones de grafo: Matriz de adyacencias

• Matriz bidimensional
• Es una representación simple
• Puede ser una representación ineficiente, si la matriz es rala

5

2

4

1

1

9

7

8

3

Representaciones de grafo: Lista de adyacencias

• Se tiene una lista principal o maestra con todos los vértices (objeto Grafo)
• Cada vértice (elemento de la lista) mantiene una lista de los vértices conectados
• Permite representar en forma compacta un grafo ralo
• Permite encontrar fácilmente todos los enlaces a partir de un vértice en particular

Implementación de un vértice

class Vertice:

def __init__(self, clave):

self.id = clave

self.conectadoA = {}

​

def agregarVecino(self, vecino, ponderacion=0):

self.conectadoA[vecino] = ponderacion

​

def __str__(self):

return str(self.id) + ' conectadoA: ' + str([x.id for x in self.conectadoA])

​

def obtenerConexiones(self):

return self.conectadoA.keys()

​

def obtenerId(self):

return self.id

​

def obtenerPonderacion(self, vecino):

return self.conectadoA[vecino]

Implementación de un grafo (incompleto)

class Grafo:

def __init__(self):

self.listaVertices = {}

self.numVertices = 0

​

def agregarVertice(self, clave):

pass

​

def obtenerVertice(self, n):

pass

​

def agregarArista(self, de, a, costo=0):

pass

​

def obtenerVertices(self):

return self.listaVertices.keys()

​

def __iter__(self):

return iter(self.listaVertices.values())

Búsqueda en anchura

Búsqueda en anchura (BEA, o BFS)

Objetivo: Explorar un grafo (o árbol) de forma expansiva, visitando todos los nodos vecinos directos de un nivel antes de pasar a los nodos más profundos.

La búsqueda en anchura es uno de los algoritmos más sencillos para buscar en grafos.

Dado un grafo G y un vértice inicial s (source), una búsqueda en anchura procede explorando las aristas en el grafo para encontrar todos los vértices en G para los cuales hay una ruta a partir de s de modo tal que todos los vértices que estén a una distancia k de s se procesan antes de encontrar cualesquiera vértices que estén a una distancia k+1.

El algoritmo utiliza una Cola (queue) como TAD auxiliar.

Recurso online: enlace a Breadth-First-Search

​

Búsqueda en anchura (BEA, o BFS) - Aplicación

Ejemplo de problema: “El problema de la escalera de palabras”

En un rompecabezas de escalera de palabras se debe transformar una palabra en otra. El cambio se hace gradualmente de a una letra a la vez.

Objetivo:

Encontrar el menor número de transformaciones para ir de una palabra inicial a una final.

Estrategia de solución:

Representar las relaciones entre las palabras como un grafo.

Usar la búsqueda en anchura para encontrar una ruta eficiente desde la palabra inicial hasta la palabra final.

Búsqueda en anchura (BEA, o BFS) - Aplicación

Representar las relaciones entre las palabras como un grafo.

Por ejemplo: POPE

Búsqueda en anchura (BEA, o BFS) - Aplicación

s (source): fool → d (destiny): sage

Búsqueda en anchura (BEA, o BFS) - Aplicación

Primer paso

Búsqueda en anchura (BEA, o BFS) - Aplicación

Segundo paso

Búsqueda en anchura (BEA, o BFS) - Aplicación

Completando el primer nivel de profundidad

Búsqueda en anchura (BEA, o BFS) - Aplicación

29

Árbol final

FOOL

POOL

POLL

POLE

PALE

PAGE

SAGE

Búsqueda en anchura (BEA, o BFS) - Implementación

La clase vértice añade tres nuevas variables de instancia: distancia, predecesor y color (blanco, gris y negro).

def bea(g,inicio):

inicio.asignarDistancia(0)

inicio.asignarPredecesor(None)

colaVertices = Cola()

colaVertices.agregar(inicio)

while (colaVertices.tamano() > 0):

verticeActual = colaVertices.avanzar()

for vecino in verticeActual.obtenerConexiones():

if (vecino.obtenerColor() == 'blanco'):

vecino.asignarColor('gris')

vecino.asignarDistancia(verticeActual.obtenerDistancia() + 1)

vecino.asignarPredecesor(verticeActual)

colaVertices.agregar(vecino)

verticeActual.asignarColor('negro')

En este caso, el algoritmo BEA utiliza una versión extendida de la clase Vertice.

Búsqueda en anchura (BEA, o BFS) - Análisis

• La inicialización es O(|V|).
• Se ejecuta un ciclo para cada vértice del grafo, por lo tanto tenemos O(|V|)
• Hay un ciclo anidado dentro del while, se ejecuta como máximo una vez para cada arista del grafo. Esto nos da O(|E|) para el ciclo for.
• Combinando los dos ciclos nos da O(|V|+|E|).
• El peor caso es que el grafo sea una única cadena. En este caso, recorrer todos los vértices es O(|V|). El caso normal será alguna fracción de |V| pero en todo caso escribiríamos O(|V|).
• También se debe tener en cuenta el tiempo requerido para construir el grafo inicial.

Búsqueda en anchura (BEA, o BFS) - Mejora y aplicación

• Una posible mejora al algoritmo consiste en contar los nodos descubiertos y detener el recorrido una vez que esta cantidad iguala a la cantidad de vértices |V| del grafo.
• Comprendiendo BEA pueden desprenderse las siguientes aplicaciones:
• Encontrar el camino de menor longitud, medida como cantidad de arcos, desde un vértice origen a uno destino. Una vez encontrado el destino, se detiene el algoritmo.
• Construir el árbol de caminos más cortos, medidos como cantidad de arcos, desde un origen hasta todos los destinos “alcanzables” desde dicho origen.

Pregunta: ¿Qué tipo de árbol genera el algoritmo BEA?

Búsqueda en profundidad

Búsqueda en profundidad (BEP, o DFS)

Objetivo: Explorar una rama o camino de principio a fin, yendo lo más profundo posible antes de retroceder (backtracking) para probar otras rutas.

La estrategia consiste en buscar lo más profundamente posible, conectando tantos nodos en el grafo como se pueda y ramificar donde sea necesario (cuando no se pueda continuar en profundidad).

La búsqueda en profundidad hace uso de los predecesores para construir un árbol.

Implementación 1: Contempla agregar dos atributos adicionales a cada Vértice.

• Tiempo de descubrimiento: rastrea el número de pasos antes de que un vértice sea encontrado por primera vez.
• Tiempo de finalización: es el número de pasos antes de que un vértice se pinte de negro.

Implementación 2: emplea estructuras auxiliares; ver recurso online: enlace a Depth-First-Search

En ambas implementaciones, el algoritmo utiliza una Pila (stack) como TAD auxiliar.

Búsqueda en profundidad (BEP, o DFS)

35

def bep(self): # self: es un Grafo. bep: produce, en este caso bosques.

for unVertice in self:

unVertice.asignarColor('blanco')

unVertice.asignarPredecesor(-1)

for unVertice in self:

if unVertice.obtenerColor() == 'blanco':

self.visitabep(unVertice)

​

def visitabep(self, verticeInicio):

verticeInicio.asignarColor('gris')

self.tiempo += 1

verticeInicio.asignarDescubrimiento(self.tiempo)

for siguienteVertice in verticeInicio.obtenerConexiones():

if siguienteVertice.obtenerColor() == 'blanco':

siguienteVertice.asignarPredecesor(verticeInicio)

self.visitabep(siguienteVertice)

verticeInicio.asignarColor('negro')

self.tiempo += 1

verticeInicio.asignarFinalizacion(self.tiempo)

Comparar con BEA

Búsqueda en profundidad (BEP, o DFS)

Búsqueda en profundidad (BEP, o DFS)

Búsqueda en profundidad (BEP, o DFS)

38

Todos los gráficos anteriores:

Búsqueda en profundidad (BEP, o DFS) - Análisis

• Los ciclos en bep se ejecutan en O(|V|), sin contar lo que ocurre en visitabep, ya que se ejecutan una vez por cada vértice en el grafo.
• En visitabep el ciclo se ejecuta una vez por cada arista en la lista de adyacencia del vértice actual.
• Dado que visitabep sólo se llama recursivamente si el vértice es blanco, el ciclo se ejecutará a lo sumo una vez por cada arista en el grafo u O(|E|).
• Por lo tanto, el tiempo total para la búsqueda de profundidad es O(|V|+|E|).

​

Búsqueda en profundidad (BEP, o DFS)

Propiedad de paréntesis

• Los descendientes de un vértice del árbol de profundidad tienen un tiempo de descubrimiento posterior y un tiempo de finalización anterior que aquellos de sus predecesores.
• Permite clasificar aristas:
• del árbol
• hacia delante
• reversa
• cruzada

Búsqueda en profundidad (BEP, o DFS) - Aplicación

Ejemplo de problema: “La gira del caballo” o “Knight’s tour”

Es la secuencia de movimientos de un caballo de ajedrez en un tablero dado, de forma que visita cada casilla una única vez.

Objetivo: Encontrar la lista de movimientos del caballo que pasa por todos los casilleros del tablero una única vez realizando movimientos válidos.

Estrategia de solución:

Representar como un grafo los movimientos legales de un caballo en un tablero de ajedrez.

Usar el algoritmo de búsqueda primero en profundidad para encontrar una ruta de longitud filas×columnas−1 donde cada vértice del grafo se visite exactamente una vez.

Búsqueda en profundidad (BEP, o DFS) - Aplicación

Es la secuencia de movimientos de un caballo de ajedrez en un tablero dado, de forma que visita cada casilla una única vez.

Camino cerrado

Camino abierto

Búsqueda en profundidad (BEP, o DFS) - Aplicación

Construcción del grafo de la gira del caballo:

El caballo se desplaza en “L” y como máximo puede tener 8 casillas vecinas.

Búsqueda en profundidad (BEP, o DFS) - Aplicación

Construcción del grafo de la gira del caballo:

• En un tablero de ocho por ocho hay 336 aristas en el grafo.
• Los vértices correspondientes a las casillas del borde del tablero tienen menos conexiones (movimientos legales) que los vértices del centro del tablero.
• Notar que el grafo es ralo: si el grafo estuviera completamente conectado, habría 4,096 aristas. Una matriz de adyacencia estaría llena sólo en un 8.2%

Búsqueda en profundidad (BEP, o DFS) - Aplicación

from pythoned.grafos import Grafo, Vertice

​

def giraCaballo(n, ruta, u, limite): # n: profundidad actual, límite: |V| (n° casilleros)

u.asignarColor('gris')

ruta.append(u)

if n < limite:

listaVecinos = list(u.obtenerConexiones())

i = 0

hecho = False

while i < len(listaVecinos) and not hecho:

if listaVecinos[i].obtenerColor() == 'blanco':

hecho = giraCaballo(n+1, ruta, listaVecinos[i], limite)

i = i + 1

if not hecho: # prepararse para retroceder

ruta.pop()

u.asignarColor('blanco')

else:

hecho = True

return hecho

Ordenamiento Topológico

Ordenamiento topológico

¿Cómo ejecutaría el siguiente algoritmo?

Receta de panqueques

Ingredientes: 1 huevo, 1 taza de mezcla de panqueques, 1 cucharada de aceite y ¾ de una taza de leche.

• Calentar una plancha
• Mezclar todos los ingredientes
• Poner la mezcla sobre una plancha caliente
• Cuando los panqueques empiecen a burbujear, darlos vuelta y dejar que se cocinen hasta que estén dorados en la parte de abajo
• Calentar un poco de almíbar o jarabe dulce
• ¡Comer! :)

Ordenamiento topológico

• Objetivo: Organizar linealmente los vértices de un GAD de modo que si existe un camino o dependencia de un vértice u a v, u siempre aparezca antes que v.
• Se parte de un grafo dirigido acíclico (GAD) y se ordenan secuencialmente todos sus vértices.
• Implementación 1: Aplica una búsqueda en profundidad para calcular los tiempos de finalización para cada uno de los vértices. Colocar los vértices en una lista en orden decreciente según el tiempo de finalización. La lista ordenada es resultado del ordenamiento topológico.
• Implementación 2: Aplica el grado de los vértices y una cola de prioridad. La idea es añadir al orden vértices de grado cero y actualizar el grado de los sucesores a medida que los predecesores se remueven de la PQ.

Recurso online: enlace a Topological Sort with DFS

Algunas conclusiones hasta ahora

Muchos problemas pueden resolverse utilizando grafos y sus algoritmos. La clave es transformar el problema (o una parte de él) para que pueda ser representado como un grafo.

Ejemplos de representaciones:

• Para palabras, se crea el grafo de "cercanía entre palabras".
• Para la gira del caballo, se usa el grafo de "movimientos legales del caballo".

La BEA es útil para encontrar la ruta no ponderada más corta entre dos vértices, medida por el número de arcos.

En el ordenamiento topológico, que se constru

Algoritmo de Dijkstra

Algoritmo de Dijkstra o “de caminos mínimos”

Objetivo: obtener la ruta más corta desde un nodo inicial dado a todos los otros nodos en un grafo ponderado con pesos no negativos.

Algoritmo de Dijkstra o “de caminos mínimos”

• Resultados similares a los de una búsqueda en anchura (BEA).
• Posee un vértice que se toma como origen y obtiene los caminos de costo mínimo hacia cada uno de los vértices restantes del grafo.
• Para el seguimiento del costo total desde el nodo inicial a cada destino, se puede utilizar un atributo “dist” en los Vértices. El orden de iteración sobre los vértices está determinado por la distancia de cada vértice al origen.
• Finalizado el algoritmo, las distancias estarán asignadas correctamente en cada vértice así como también los enlaces a los predecesores → Árbol de caminos mínimos.

Algoritmo de Dijkstra - Implementación

1: from pythoned.grafos import ColaPrioridad, Grafo, Vertice

2:

3: def dijkstra(unGrafo, inicio):

4: cp = ColaPrioridad()

5: inicio.asignarDistancia(0)

6: cp.construirMonticulo([(v.obtenerDistancia(),v) for v in unGrafo])

7:

8: while not cp.estaVacia():

9: verticeActual = cp.eliminarMin()

10:

11: for verticeSiguiente in verticeActual.obtenerConexiones():

12: nuevaDistancia = verticeActual.obtenerDistancia()

13: + verticeActual.obtenerPonderacion(verticeSiguiente)

14: if nuevaDistancia < verticeSiguiente.obtenerDistancia():

15: verticeSiguiente.asignarDistancia(nuevaDistancia)

16: verticeSiguiente.asignarPredecesor(verticeActual)

17: cp.decrementarClave(verticeSiguiente,nuevaDistancia)

Algoritmo de Dijkstra - Implementación

1: from pythoned.grafos import ColaPrioridad, Grafo, Vertice

2:

3: def dijkstra(unGrafo, inicio):

4: cp = ColaPrioridad()

5: inicio.asignarDistancia(0)

6: cp.construirMonticulo([(v.obtenerDistancia(),v) for v in unGrafo])

7:

8: while not cp.estaVacia():

9: verticeActual = cp.eliminarMin()

10:

11: for verticeSiguiente in verticeActual.obtenerConexiones():

12: dist_u = verticeActual.obtenerDistancia()

13: dist_uv = verticeActual.obtenerPonderacion(verticeSiguiente)

14: dist_v = verticeSiguiente.obtenerDistancia()

15: # debe cumplirse para todo vértice que “dist_v <= dist_u + dist_uv”

16: if dist_v > dist_u + dist_uv:

17: verticeSiguiente.asignarDistancia(dist_u + dist_uv)

18: verticeSiguiente.asignarPredecesor(verticeActual)

19: cp.decrementarClave(verticeSiguiente,dist_u + dist_uv)

Algoritmo de Dijkstra - Ejemplo

55

Algoritmo de Dijkstra - Recurso online

Recurso online: enlace a Dijkstra

Algoritmo de Dijkstra - Análisis

• Construir la cola de prioridad toma un tiempo O(|V|)
• El ciclo while se ejecuta una vez para cada vértice. Dentro del ciclo, cada llamada a eliminarMin toma un tiempo O(log |V|). Por lo tanto, el conjunto toma un tiempo O(|V| log |V|)
• El ciclo for se ejecuta una vez por cada arista en el grafo, y dentro del ciclo for la llamada a decrementarClave toma un tiempo O(|E| log |V|)
• El tiempo de ejecución combinado es O((|V|+|E|) log |V|)

Algoritmo de Prim

Algoritmo de Prim

Objetivo (Conceptual): encontrar el Árbol de Expansión Mínima (MST) en un grafo conexo y no dirigido.

Objetivo (Aplicación): transferir eficientemente una pieza de información a todos y cada uno de los nodos conectados.

Este algoritmo de grafos se aplica a un tipo de problema que enfrentan diseñadores de juegos en línea y proveedores de radio por Internet.

Otra aplicación es el ruteo de pistas de un circuito electrónico empleando la mínima cantidad posible de pista.

​

Algoritmo de Prim

¿Cómo plantearía la solución a este problema?

Recordar: El objetivo es transferir una pieza de información a todos los nodos conectados.

Suponer que los pesos representan la demora en la transmisión de un nodo a otro.

​

Algoritmo de Prim

¿Cómo plantearía la solución a este problema?

Recordar: El objetivo es transferir una pieza de información a todos los nodos conectados.

Suponer que los pesos representan la demora en la transmisión de un nodo a otro.

​

Algoritmo de Prim

El algoritmo se basa en la construcción de un árbol de expansión de costo mínimo (AEM), o árbol de expansión de ponderación mínima.

Dado un grafo conexo G=(V,E), el AEM es un árbol T generado a partir de G como un subconjunto acíclico de E que conecta todos los vértices de V, y minimiza la suma de las ponderaciones de las aristas de T.

Algoritmo de Prim - Ejemplo

d=1

d=4

d=1

d=1

d=4

d=5

d=1

d=1

d=1

d=1

d=1

d=1

d=1

d=1

d=5

d=1

d=1

d=1

d=1

d=1

d=1

d=1

d=1

d=1

d=1

Algoritmo de Prim - Recurso online

Recurso online: enlace a Prim

Algoritmo de Prim - Implementación

01: def prim(G, inicio):

02: cp = ColaPrioridad()

03:

04: for v in G:

05: v.asignarDistancia(sys.maxsize)

06: v.asignarPredecesor(None)

07:

08: inicio.asignarDistancia(0)

09: cp.construirMonticulo([(v.obtenerDistancia(),v) for v in G])

10:

11: while not cp.estaVacia():

12: verticeActual = cp.eliminarMin()

13: for verticeSiguiente in verticeActual.obtenerConexiones():

14: nuevoCosto = verticeActual.obtenerPonderacion(verticeSiguiente)

15: if verticeSiguiente in cp and nuevoCosto < verticeSiguiente.obtenerDistancia():

16: verticeSiguiente.asignarPredecesor(verticeActual)

17: verticeSiguiente.asignarDistancia(nuevoCosto)

18: cp.decrementarClave(verticeSiguiente,nuevoCosto)

Algoritmo de Prim - Análisis

• Construir la cola de prioridad toma un tiempo O(|V|)
• El ciclo while se ejecuta una vez para cada vértice. Dentro del ciclo, cada llamada a eliminarMin toma un tiempo O(log |V|). Por lo tanto, el conjunto toma un tiempo O(|V| log |V|)
• El ciclo for se ejecuta una vez por cada arista en el grafo, y dentro del ciclo for la llamada a decrementarClave toma un tiempo O(|E| log |V|)
• El tiempo de ejecución combinado es O((|V|+|E|) log |V|)
• Si |E| >> |V|, entonces, el orden de complejidad tiende a O(|E| log |V|)

Algoritmo de Warshall

Algoritmo de Warshall

Otra aplicación importante de Grafos es el cálculo de la Cerradura Transitiva (Transitive Closure).

Se aplica, principalmente, sobre Grafos dirigidos. Sirve para determinar si existe o no una trayectoria entre dos vértices cualesquiera del grafo.

Es una operación importante en problemas de Conectividad y Ruteo.

La Cerradura Transitiva se basa en lo siguiente:

Si existe una trayectoria de N_j a N_k y existe una trayectoria entre N_k y N_p, entonces, existirá una trayectoria entre N_j y N_p.

Existen diferentes algoritmos para determinar si existe un camino entre dos Nodos, sin embargo, el más común es denominado el algoritmo de Warshall.

Algoritmo de Warshall

Sea un grafo G = (V, E)

Se define la cerradura transitiva como el grafo G* = (V, E*) donde

E* = { (i, j) : hay un camino desde el vértice i al vértice j en G}

Para construir el algoritmo, dados i, j, k = 1, 2, …, n definimos

t_ij^(k) de modo que sea 1 si existe un camino de i a j en el grafo G con todos los vértices intermedios en el conjunto {1, 2, …, k}, o 0 en otro caso

Para construir la cerradura transitiva G* = (V, E*) agregar (i, j) en E* si y solo si t_ij⁽ⁿ⁾ = 1

Algoritmo de Warshall

Una definición recursiva de lo enunciado anteriormente es:

​

​

​

​

​

Por lo tanto, el algoritmo de cerradura transitiva computa las matrices T^(k) = (t_ij^(k)) conforme k crece. A continuación el pseudocódigo del algoritmo.

Algoritmo de Warshall - Pseudocódigo

sea T⁽⁰⁾ = (t_ij⁽⁰⁾) una nueva matriz n x n

# inicialización

para i = 1 a n

para j = 1 a n

si i = j o (i,j) en G.E, entonces, t_ij⁽⁰⁾ = 1

sino, entonces, t_ij⁽⁰⁾ = 0

# recurrencia

para k = 1 a n

sea T^(k) = (t_ij^(k)) una nueva matriz n x n

para i = 1 a n

para j = 1 a n

t_ij^(k) = t_ij^(k-1) v (t_ik^(k-1)∧ t_kj^(k-1)) # v es or y ∧ es and

retornar T⁽ⁿ⁾

Algoritmo de Warshall - Ejemplo en pizarra

Algoritmo de Warshall - Ejemplo 1

Caso de ejemplo:

Matriz de Adyacencias

Corresponde a T⁽⁰⁾ = (t_ij⁽⁰⁾)

luego de inicializarla con los arcos E del grafo G

G

Algoritmo de Warshall - Ejemplo 1

Caso de ejemplo:

T⁽⁰⁾ = (t_ij⁽⁰⁾)

T⁽¹⁾ = (t_ij⁽¹⁾)

T⁽²⁾ = (t_ij⁽²⁾)

T⁽³⁾ = (t_ij⁽³⁾)

T⁽⁴⁾ = (t_ij⁽⁴⁾)

Algoritmo de Warshall - Ejemplo 1

Caso de ejemplo:

Matriz de Adyacencias

Corresponde a T⁽⁰⁾ = (t_ij⁽⁰⁾)

luego de inicializarla con los arcos E del grafo G

Matriz de cerradura transitiva

G

G*

Algoritmo de Warshall - Ejemplo 2

Caso de ejemplo: En este caso se asume que NO se puede ir un nodo a sí mismo.

Matriz de Adyacencias

Corresponde a T⁽⁰⁾ = (t_ij⁽⁰⁾)

luego de inicializarla con los arcos E del grafo G

Matriz de cerradura transitiva

G

G*

Algoritmo de Warshall - Implementación

A partir de la representación en Matriz de Adyacencias de un digrafo, obtiene la Matriz que representa a su Cerradura Transitiva y es de orden O(|V|³)

​

# El resultado del algoritmo queda almacenado en la matriz T

1: def calcular_matriz_de_cerradura_transitiva(G):

2: V = G[0]

3: E = G[1]

4: n = len(V)

5: T = np.array([0 for i in range(n) for j in range (n)]).reshape(n,n)

6: for v in V:

7: T[v-1, v-1] = True

8: for e in E:

9: T[e[0]-1, e[1]-1] = True

10: for k in range(0,n):

11: for i in range(0,n):

12: for j in range(0,n):

13: T[i,j] = T[i,j] or (T[i,k] and T[k, j])

14: return T

Comentarios finales

Estudiamos el tipo abstracto de datos Grafo y algunas implementaciones.

Un grafo permite resolver muchos problemas siempre que podamos transformar el problema original en algo que puede ser representado por un grafo.

Particularmente estudiamos los problemas en las siguientes áreas generales:

• Búsqueda en anchura para encontrar la ruta no ponderada más corta.
• El algoritmo de Dijkstra para la ruta ponderada más corta.
• Búsqueda en profundidad para la exploración de grafos.
• Ordenamiento topológico para ordenar tareas.
• Árboles de expansión de ponderación mínima para radiodifusión de mensajes.

Bibliografía

• Bradley N. Miller, David L. Ranum. Solución de problemas con algoritmos y estructuras de datos usando Python. Luther College. Traducido por Mauricio Orozco-Alzate, Universidad Nacional de Colombia - Sede Manizales. 2018. Sección 7. Enlace: enlace - Capítulo 7
• Recursos online:
• BFS: https://www.cs.usfca.edu/~galles/visualization/BFS.html
• DFS: https://www.cs.usfca.edu/~galles/visualization/DFS.html
• Ordenamiento topológico con DFS: https://www.cs.usfca.edu/~galles/visualization/TopoSortDFS.html
• Dijkstra: https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html
• Prim: https://www.cs.usfca.edu/~galles/visualization/Prim.html
• Para investigar un poco más: Análisis Comparativo de Algoritmos de Minería de Subgrafos Frecuentes, (Link 1, Link2), Santiago Bianco, Revista Latinoamericana de Ingeniería de Software, 2016.

Fin presentación

Algoritmos y Estructuras de Datos