SLIDES - Tecnología Digital V Diseño de Algoritmos (8)

Vista previa del material en texto

ALGORITMOS SOBRE GRAFOS: BFS, DFS.
Tecnología Digital V: Diseño de Algoritmos
Universidad Torcuato Di Tella
Motivación
Definiciones
# Un grafo es conexo si existe un camino entre todo par de vértices.
# Una componente conexa es un subconjunto de vértices conexo, maximal
con esta propiedad.
# Un vértice aislado es un vértice 8 con 3(8) = 0 (que conforma una
componente conexa de tamaño 1).
1
3
2 4
6
5
7
Conexo
1
3
2 4
6
5
7
No conexo
Preguntas
# Ideas para diseñar un algoritmo que verifique si un grafo es conexo?
# Podremos adaptarlo para obtener las componentes conexas de un grafo?
TD5: Diseño de Algoritmos - UTDT 2
Recorrido de un grafo
Idea intuitiva
Dado un grafo � = (+, �)
1. partimos de un vértice arbitrario B ∈ + ;
2. idenficamos todos los vecinos que se puede alcanzar desde B;
3. si � es conexo existe un camino entre B y todos los demás vértices;
4. verificamos si los vértices alcanzables son todos los vértices (i.e., +).
1
3
2 4
6
5
7
Supongamos que iniciamos con B = 1
# Cómo podemos encontrar todos
los vértices alcanzables desde 1
de forma sistemática?
# Qué situaciones particulares se
pueden dar durante el proceso?
TD5: Diseño de Algoritmos - UTDT 3
Recorrido de un grafo
Recorrido(� = (+, �), B ∈ +)
estado = vector(|+ |)
for E ∈ + do
estado[v] = no descubierto
end for
estado[s] = descubierto
! = [B] ⊲ ! tiene los vertices a procesar
while ! ≠ ∅ do
Sea E el siguiente elemento en !
for F ∈ #(E) do
if estado[F] = no descubierto then
estado[F] = descubierto
Agregar F a !
end if
end for
estado[v] = procesado
Eliminar a E de !
end while
return estado
En cada iteración, un vértice puede
tener 1 de 3 posibles estados:
# no descubierto: todavía no
ha sido visitado por el
algoritmo.
# descubierto: visitado por
ser vecino de otro vértice,
pero no procesado.
# procesado: sus vecinos han
sido descubiertos.
Al terminar el algoritmo, verifi-
camos que estado[E] == procesado
∀E ∈ + .
TD5: Diseño de Algoritmos - UTDT 4
Recorrido de un grafo
Algunas propiedades
# En el ciclo while, ! contiene solamente vértices E ∈ + tales que
estado[E] = descubierto.
# Al finalizar el algoritmo, estado[E] ∈ {no descubierto, procesado}.
# Los vértices E ∈ + tales que estado[E] = procesado conforman una
componente conexa.
Preguntas
# Cuántas veces se ejecuta el ciclo while exterior en peor caso?
# Cuál es la complejidad de obtener los vecinos de E, #(E)?
TD5: Diseño de Algoritmos - UTDT 5
Recorrido de un grafo: complejidad computacional
Sea |+ | = = y |� | = <.
Recorrido(� = (+, �), B ∈ +)
estado = vector(|+ |)
for E ∈ + do ⊲ Incialización.
estado[v] = no descubierto
end for
estado[s] = descubierto
! = [B]
while ! ≠ ∅ do ⊲ Vértices descubiertos a procesar.
Sea E el siguiente elemento en ! ⊲ Procesamos el siguiente vértice.
for F ∈ #(E) do ⊲ Descubrimos los vecinos de E.
if estado[F] = no descubierto then
estado[F] = descubierto
Agregar F a !
end if
end for
estado[v] = procesado ⊲Marcamos E como procesado.
Eliminar a E de !
end while
return estado
TD5: Diseño de Algoritmos - UTDT 6
Recorrido de un grafo: complejidad computacional
Sea |+ | = = y |� | = <. � implementado sobre matriz de adyacencia.
Recorrido(� = (+, �), B ∈ +)
estado = vector(|+ |)
for E ∈ + do ⊲ $(=).
estado[v] = no descubierto
end for
estado[s] = descubierto
! = [B]
while ! ≠ ∅ do ⊲ $(=).
Sea E el siguiente elemento en !
for F ∈ #(E) do ⊲ $(=).
if estado[F] = no descubierto then
estado[F] = descubierto ⊲ $(1).
Agregar F a ! ⊲ $(1).
end if
end for
estado[v] = procesado ⊲ $(1).
Eliminar a E de !
end while
return estado
TD5: Diseño de Algoritmos - UTDT 7
Recorrido de un grafo: complejidad computacional
Sea |+ | = = y |� | = <. � implementado sobre lista de vecinos.
Recorrido(� = (+, �), B ∈ +)
estado = vector(|+ |)
for E ∈ + do ⊲ $(=).
estado[E] = no descubierto
end for
estado[B] = descubierto
! = [B]
while ! ≠ ∅ do ⊲ $(=).
Sea E el siguiente elemento en !
for F ∈ #(E) do ⊲ Obtener #(E) es $(1). Recorrerla, $(3(E)).
if estado[F] = no descubierto then
estado[F] = descubierto ⊲ $(1).
Agregar F a ! ⊲ $(1).
end if
end for
estado[v] = procesado ⊲ $(1).
Eliminar a E de !
end while
return estado
TD5: Diseño de Algoritmos - UTDT 8
Recorrido de un grafo: complejidad computacional
Matriz de adyacencia
# Obtener los vecinos: $(=)
# Recorrer la lista de vecinos de E:
$(3(E))
# Descubrir / procesar todos los
vértices: $(=2)
# Algoritmo completo:
$(=) + $(=2) = $(=2)
Lista de vecinos
# Obtener los vecinos: $(1)
# Recorrer la lista de vecinos de E:
$(3(E))
# Descubrir / procesar todos los
vértices:
∑
E∈+ 3(E)
# Algoritmo completo:
$(=) + $(∑E∈+ 3(E)) = ?
Handshaking Lemma
Sea � = (+, �) un grafo con < = |� | la cantidad de aristas. Entonces,∑
E∈+
3(E) = 2<
TD5: Diseño de Algoritmos - UTDT 9
Recorrido de un grafo: complejidad computacional
Resumiendo:
1. $(=2) si el grafo está implementado sobre una matriz de adyacencia.
2. $(<) si el grafo está implementado sobre listas de vecinos.
Es habitual escribir la complejidad de algoritmos sobre grafos en función de
= = |+ | y < = |� |.
1. En general, < = $(=2), con lo cual el peor caso es el mismo para ambas
implementaciones.
2. Si < = $(=), decimos que el grafo es poco denso y entonces conviene la
segunda implementación.
Ejemplo: sabemos que cada vértices está conectado con a lo sumo : vecinos, con
: acotado.
Ejercicio (6, guía 2)
Cómo re-usamos Recorrido(�, B) para obtener todas las componentes
conexas de un grafo?
TD5: Diseño de Algoritmos - UTDT 10
Tipos de recorridos
1
3
2 4
6
5
7
# BFS(�,E): Si la lista ! se implementa con una cola (queue), entonces el
algoritmo recorre el grafo a lo ancho y se lo llama (breadth-first search).
# DFS(�,E): Si la lista ! se implementa con una pila (stack), entonces el
algoritmo recorre el grafo en profundidad y se lo llama (depth-first
search).
Pregunta
Si quisiéramos calcular la distancia de un vértice E a otro F, que esquema
nos convenddría usar?
TD5: Diseño de Algoritmos - UTDT 11
Recorrido de un grafo: complejidad computacional
BFS(� = (+, �), B ∈ +)
estado = vector(|+ |), dist = vector(|+ |)
for E ∈ + do
estado[E] = no descubierto
dist[E] = ∞
end for
estado[B] = descubierto, dist[B] = 0
! = Queue(), Agregar B a !.
while ! ≠ ∅ do
Sea E el siguiente elemento en !
for F ∈ #(E) do
if estado[F] = no descubierto then
estado[F] = descubierto
dist[F] = dist[E] + 1
Agregar F a !
end if
end for
estado[v] = procesado
Eliminar a E de !
end while
return estado, dist
TD5: Diseño de Algoritmos - UTDT 12
Tipos de recorridos
1
3
2 4
6
5
7
# BFS(�,E): Si la lista ! se implementa con una cola (queue), entonces el
algoritmo recorre el grafo a lo ancho y se lo llama (breadth-first search).
Recorre los vértices en orden de distancia creciente desde B.
# DFS(�,E): Si la lista ! se implementa con una pila (stack), entonces el
algoritmo recorre el grafo en profundidad y se lo llama (depth-first
search).
Encuentra primero el vértice más lejano a B.
TD5: Diseño de Algoritmos - UTDT 13