Upload
fabian-orccon
View
221
Download
0
Embed Size (px)
Citation preview
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
1/40
1
Profesor:Mag. Fernando Alva Manchego
Pontificia Universidad Catlica del PerFacultad de Ciencias e Ingeniera
Especialidad de Ingeniera Infor!ticaCurso: AlgoritiaCaptulo ": Aplicaciones de Estructuras de #atos
$%&'($
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
2/40
2
)rafos
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
3/40
3
#efinicin
Un grafo G = (V, E) est definido por el par deconjuntos:
*: conjunto finito no vaco de eleentos llaadosv+rtices
E: conjunto de pares de v!rtices llaados aristas
LEVITIN, A. Introduction to The Design and Analysis of Algorithms. 3ra edicin.
USA: Pearson, 2012. ISBN-13 9!-0-13-231"!1-1
a c #
d e $
V={a,b,c,d,e,f}
E={(a,c),(a,d),(b,c),(b,f),(c,e),(d,e),(e,f)}
GrafoG
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
4/40
"
)rafos ,o #irigidos
#i las aristas (u, v)$ (v, u) son las isas, se dice%ue los v!rtices u$ vson ad-acentes$ %ue estnconectados por la arista no dirigida(u, v)
Un &rafo Ges llaado no dirigidosi cada una desus aristas es no diri&ida
LEVITIN, A. Introduction to The Design and Analysis of Algorithms. 3ra edicin.
USA: Pearson, 2012. ISBN-13 9!-0-13-231"!1-1
a c #
d e $
V={a,b,c,d,e,f}
E={(a,c),(a,d),(b,c),(b,f),(c,e),(d,e),(e,f)}
Grafo no dirigidoG
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
5/40
'
)rafos #irigidos o #igrafos
#i las aristas (u, v)$ (v, u) no son las isas, sedice %ue la arista (u, v) est dirigidadesde elv!rtice u
Un &rafo es llaado dirigido(o digrafo) si todassus aristas son diri&idas
a c #
d e $
V={a,b,c,d,e,f}
E={%a,c&,%#,c&,%#,$&,%c,e&,%d,a&,%d,e&,%e,c&,%e,$&}
Grafo dirigidoG
LEVITIN, A. Introduction to The Design and Analysis of Algorithms. 3ra edicin.
USA: Pearson, 2012. ISBN-13 9!-0-13-231"!1-1
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
6/40
erinologa
Un &rafo con todos sus pares de v!rticesconectados por una arista es llaado copleto
LEVITIN, A. Introduction to The Design and Analysis of Algorithms. 3ra edicin.
USA: Pearson, 2012. ISBN-13 9!-0-13-231"!1-1
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
7/40
erinologa
Un &rafo con relativaente pocas aristas faltanteses llaado denso
Un &rafo con pocas aristas relativas al n*ero de
sus v!rtices es llaado esparso
es'arso denso
LEVITIN, A. Introduction to The Design and Analysis of Algorithms. 3ra edicin.
USA: Pearson, 2012. ISBN-13 9!-0-13-231"!1-1
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
8/40+
/epresentacin de
)rafos
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
9/40
A# )rafo: 0peraciones
-rear un &rafo vaco .nsertar una arista en un &rafo
.nsertar un v!rtice en un &rafo
Verificar si e/iste deterinada arista en el &rafo Verificar si e/iste deterinado v!rtice en el &rafo
Eliinar una arista del &rafo
Eliinar un v!rtice del &rafo .priir un &rafo
0tener el n*ero de v!rtices del &rafo
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
10/401
A# )rafo: 1Co se representa2
a selecci4n de la estructura de datos correcta pararepresentar &rafos tiene un ipacto enore en el
desepe5o de un al&orito
6epresentaciones usuales:
7atri8 de ad$acencia
Estructura de ad$acencia (con listas de ad$acencia)
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
11/4011
Matri3 de Ad-acencia
9ado un &rafo G = (V, E), la atri3 de ad-acenciaMes una atri8 de orden n x n, tal %ue: n= n*ero de v!rtices M4i5 67 8 &, si e/iste la arista del nodo ial nodoj M4i5 67 8 %, si no e/iste la arista del nodo ial nodoj
a c #
d e $
1 1
1 1
1 1 1
1 1
1 1 1
1 1
a
b
c
d
e
f
a b c d e f
M =
G = (V, E)
LEVITIN, A. Introduction to The Design and Analysis of Algorithms. 3ra edicin.
USA: Pearson, 2012. ISBN-13 9!-0-13-231"!1-1
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
12/4012
Matri3 de Ad-acencia
Es la fora s siple de representaci4n
ropiedades:
Es si+tricapara un &rafo no diri&ido M[i, j] = M[j, i], para todo 0
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
13/4013
Estructura de Ad-acencia
9ado un &rafo G = (V, E), la estructura dead-acencia A es conjunto de n listas A(v), una
para cada v!rtice v%ue pertenece a V
-ada listaA(v)es llaada lista de ad-acencia delv!rtice v$ contiene los v!rtices wad$acentes a v
en G
a c #
d e $
G = (V, E)
a
b
c
d
e
f
c d
c f
a b e
a e
c d f
b e
A =
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
14/401"
19 para un grafo dirigido2
a c #
d e $
G = (V, E)
&
& &
&
& &
& &
a
b
c
d
e
f
a b c d e f
M =
a
b
c
d
e
f
c
c f
e
a e
c f
A =
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
15/401'
Estructura de Ad-acencia
6epresentaci4n s elaorada
ropiedades:
;lacenaiento: 0(
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
16/40
1
Coparacin de /epresentaciones
Caracterstica Matri3 deAd-acencia
ista deAd-acencia
Alacenaiento 0(
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
17/40
1
1Cu!ndo usar cada representacin2
#i un &rafo es esparso, la representaci4n por listasde ad$acencia podra usar enos espacio %ue su
correspondiente atri8 de ad$acencia> la situaci4n
es e/actaente opuesta para &rafos densos
En &eneral, cul de las dos representaciones es
s conveniente depende de la naturale8a del
prolea, el al&orito usado para resolverlo $,posileente, el tipo de &rafo (esparso o denso)
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
18/40
1+
/ecorrido de )rafos
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
19/40
1
/ecorriendo un )rafo
6ecorrer un &rafo es un prolea fundaental
#e dee tener una fora sistetica de visitar las
aristas $ los v!rtices
El al&orito dee ser lo suficienteente fle/ile
para adecuarse a una diversidad de &rafos
Eficacia:?o dee @aer repeticiones (innecesarias) devisitas a un v!rtice $Ao arista
Correctitud: Bodos los v!rtices $Ao aristas deen servisitados
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
20/40
2
Estrategia )eneral
7arcar los v!rtices coo ?o visitados
Visitados
rocesados
C
#i se antiene una lista de v!rtices !"ce#ad"#
e/isten dos posiilidades de ipleentaci4n:
-ola ila
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
21/40
21
=F>: =readth(First >earch
D*s%ueda en aplitud (o por niveles) Estructuras de datos $ variales:
Por *isitar:-ontiene la cola de v!rtices del &rafo %uevan siendo procesados $ a*n faltan visitar
*isitados:-ontiene toda la lista de nodos %ue @an sidovisitados a lo lar&o del al&orito
P: V!rtice del &rafo %ue est siendo procesado en cadapaso (iteraci4n)
?i6os@P: ista de nodos ad$acentes a *+rtice Inicial - *+rtice Final >entidode lectura (@orarioAanti@orario)
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
22/40
22
=F>: =readth(First >earch
Inicio=F>(Grafo, orVisitar, Vertice.ni, Verticein, #entido)
Cola@Iniciali3ar(orVisitar)
ista@Iniciali3ar(Visitados)
Cola@Enueue(Vertice.ni, orVisitar)
MientrasCola@Es*acia(orVisitar) = FA>09 F Verticein hacer
= Cola@#eueue(orVisitar) $!"ce#a!
ista@Insertar(Visitados, )
HijosI = )rafo@Ad-acentes(Grafo, , #entido)
Paracadau HijosI A u Visitados hacerCola@Enueue(orVisitar, u)
FinMientras
Fin=F>
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
23/40
23
E6eplo =F>
6ecorra el si&uiente &rafo con D# coen8andopor el v!rtice a $ uscando el v!rtice f:
a c #
d e $
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
24/40
2"
#F>: #epth(First >earch
D*s%ueda en profundidad Estructuras de datos $ variales:
Por *isitar:-ontiene la pila de v!rtices del &rafo %uevan siendo procesados $ a*n faltan visitar
*isitados:-ontiene toda la lista de nodos %ue @an sidovisitados a lo lar&o del al&orito
P: V!rtice del &rafo %ue est siendo procesado en cadapaso (iteraci4n)
?i6os@P: ista de nodos ad$acentes a *+rtice Inicial - *+rtice Final >entidode lectura (@orarioAanti@orario)
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
25/40
2'
#F>: #epth(First >earch
Inicio#F>(Grafo, orVisitar, Vertice.ni, Verticein, #entido)
Pila@Iniciali3ar(orVisitar)
ista@Iniciali3ar(Visitados)
Pila@Push(Vertice.ni, orVisitar)
MientrasPila@Es*acia(orVisitar) = FA>09 F Verticein hacer
= Pila@Pop(orVisitar) $!"ce#a!
ista@Insertar(Visitados, )
HijosI = )rafo@Ad-acentes(Grafo, , #entido)
Paracadau HijosI A u Visitados hacerPila@Push(orVisitar, u)
FinMientras
Fin#F>
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
26/40
2
E6eplo #F>
6ecorra el si&uiente &rafo con 9# coen8andopor el v!rtice a $ uscando el v!rtice f:
a c #
d e $
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
27/40
2
Cainos M!s Cortos
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
28/40
2+
Aplicacin en Mapas
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
29/40
2
Aplicaciones picas
Aplicacin *+rtice Arista
7apa .ntersecci4n -aino
6ed %"u&e! -one/i4n
ro&raaci4n de@orarios
Barea 6estricci4n deprecedencia
;ritrajeJ 7oneda Bipo de caio
'En ec"n"a * finan+a#, arbitrajee# a !-c&ica de &"a! ven&aja de una
dife!encia de !eci" en&!e d"# " -# e!cad"#. !eai+a! una c"binaci/n
de &!an#acci"ne# c"een&a!ia# ue cai&ai+an e de#euiib!i" de "#
!eci"#
SE()E*I+, . *A/NE, . Algorithms. a edicin. USA: Pearson, 2011.
ISBN-13 9!-0-321-31-3
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
30/40
3
#efinicin
El caino !s corto desde el v!rtice # @asta elv!rtice & en un di&rafo ponderado es un cainodiri&ido desde#@asta &con la propiedad de %ue no
otro caino tiene un peso enor
SE()E*I+, . *A/NE, . Algorithms. a edicin. USA: Pearson, 2011.
ISBN-13 9!-0-321-31-3
1
3
"
2
0
K3'K3' K3
K2+
K2+
K32
K3+
K2(
2K3,
K2,
2K3"
2K"2
K'2
2K'+
K3
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
31/40
31
1Cu!l es el caino !s corto de % a B2
13
"
2
0
K3'K3' K3
K2+
K2+
K32
K3+
K2(
2K3,
K2,
2K3"
2K"2
K'2
2K'+
K3
-aino 7s -orto de a :
2 K2
2 K3"
3 K3
3 K'2
SE()E*I+, . *A/NE, . Algorithms. a edicin. USA: Pearson, 2011.
ISBN-13 9!-0-321-31-3
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
32/40
32
*ariantes
#esde un nico origen Encontrar los cainos s cortos desde un v!rtice
ori&en#a todos los des v!rtices del &rafo
Con un nico destino Encontrar los cainos s cortos desde todos los
v!rtices del &rafo a un *nico v!rtice destino
Entre un nico par de v+rtices Encontrar el caino s corto entre los v!rtices u$ v
Entre todos los pares de v+rtices Encontrar los cainos s cortos entre cada par de
v!rtices u$ vdel &rafo
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
33/40
33
Algorito de #i6stra
;plicale en &rafos diri&idos $ no diri&idos con
pesos no ne&ativos
.dea sica:
#e inicia desde un v!rtice#
#e posee un conjunto de v!rtices para cuales conoceos
sus cainos s cortos desde#(inicialente vaco)
En cada iteraci4n, se a5ade a este conjunto a%uel v!rtice
uad$acente al v!rtice actual u'%ue est! s cerca de#
#e dee considerar la distancia desde # @asta el v!rtice
actual u'$ el peso de la arista (u, u')
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
34/40
3"
E6eplo &
Hallar los cainos s cortos desde el v!rtice a
LEVITIN, A. Introduction to The Design and Analysis of Algorithms. 3ra edicin.
USA: Pearson, 2012. ISBN-13 9!-0-13-231"!1-1
a
# c
d e
2
3 "
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
35/40
3'
E6eplo &: >olucin
*isitados Por *isitar
a(L,)
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
36/40
3
E6eplo $
Hallar los cainos s cortos desde el v!rtice &
1
2
9
!
2
11
3
1
!
3
"
"2
1
9
10
Era4do de: 5':66777.8ees$or8ees.or868reed-a8ori5;s-se-"-di
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
37/40
3
E6eplo $: >olucin
Hallar los cainos s cortos desde el v!rtice &
1
2
9
!
3 !
!
0
3
"
11
10
1
21
9
Era4do de: 5':66777.8ees$or8ees.or868reed-a8ori5;s-se-"-di
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
38/40
3+
Eficiencia del Algorito de #i6stra
a ipleentaci4n s siple: El conjunto de v!rtices ,o*isitadoses una lista enla8ada o un
arre&lo
E/traer el nio de ,o*isitadoses una *s%ueda lineal
0(
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
39/40
3
Jr
7/23/2019 CAP5 Aplicaciones de Estructuras de Datos - Grafos
40/40
Contacto
Mag. Fernando Alva Manchegoontificia Universidad -at4lica del er*
9epartaento de .n&eniera
#ecci4n de .n&eniera .nforticafKalvaNpucpKpe