Download Algoritmos y estructuras de datos - Cinvestav

Algoritmos y estructuras de datos
Dr. Eduardo A. Rodríguez Tello
Laboratorio de Tecnologías de Información
Cinvestav Tamaulipas
Cinvestav‐Tamaulipas
[email protected]
Cursos de inducción a la MCC
© Cinvestav‐Tamaulipas 2012
1
Temario
I.
II.
III.
Introducción
Estructuras de datos estáticas y dinámicas
Tipos de datos abstractos
a.
b.
c.
d.
e.
IV.
V.
VI.
Listas
Colas
Pilas
Arboles
Grafos
Ordenamientos
Búsquedas
Resumen
Cursos de inducción a la MCC
Estructuras de datos
© Cinvestav‐Tamaulipas 2012 2
Arboles
Un árbol es un conjunto finito de nodos:
1. Si la colección es vacía,
1
vacía se dice que el árbol es vacío
2. En caso contrario, un árbol A consiste de un nodo especial
llamado raíz y n (sub)árboles no vacíos T1,T2,…,Tn. La raíz de
A se conecta con la raíz de cada Ti por un arco dirigido
A
B
E
Cursos de inducción a la MCC
C
F
Estructuras de datos
D
G
H
© Cinvestav‐Tamaulipas 2012 3
Relaciones entre nodos
Todo nodo nj, exceptuando el raíz, está conectado
exclusivamente a otro nodo nk donde:




nj es el padre de nk (e.g., B es el padre de E)
j de nj ((e.g.,
g E es un hijo
j de B))
nk es uno de los hijos
Nodos con el mismo padre son “hermanos” (e.g. B y C)
Nodos sin hijos son llamados “hojas” (e.g. G)
A
B
E
Cursos de inducción a la MCC
Estructuras de datos
C
F
D
G
© Cinvestav‐Tamaulipas 2012 H
4
Árboles binarios
• Un árbol binario es un árbol en el cual cada
árbol en el cual cada nodo puede tener como máximo dos hijos
• Un árbol binario se define como:
– un árbol vacío, o – un nodo raíz con un s bárbol i q ierdo n
subárbol izquierdo y un subárbol derecho
Cursos de inducción a la MCC
Raíz
25
36
10
Árbol
izquierdo
Estructuras de datos
64
15
8
30
Árbol
derecho
© Cinvestav‐Tamaulipas 2012 5
Operaciones básicas en árboles





Crear un árbol vacío
Verificar si el árbol está vacío
Insertar un nodo
Eli i
Eliminar
un nodo
d
Recorrer un árbol
Cursos de inducción a la MCC
Estructuras de datos
© Cinvestav‐Tamaulipas 2012 6
Recorridos de árboles


Procedimientos que visitan todos los nodos de un árbol
efectuando una acción sobre cada uno
Existen dos formas posibles de recorrer un árbol no vacío
 Amplitud: el proceso se realiza horizontalmente desde la raíz a todos sus
hijos luego a los hijos de sus hijos y así sucesivamente
hijos,
 Profundidad: se sigue un camino desde la raíz a través de un hijo antes
de proseguir al siguiente hijo
Cursos de inducción a la MCC
Estructuras de datos
© Cinvestav‐Tamaulipas 2012 7
Ejemplo de recorrido en amplitud
A
B
D
C
E
F
G
A B,
A,
B C,
C D,
D E
E, F
F, G
Cursos de inducción a la MCC
Estructuras de datos
© Cinvestav‐Tamaulipas 2012 8
Recorridos en profundidad

Existen tres formas posibles de recorrer en profundidad un
árbol no vacío, según cuando la raíz sea visitada
Primer orden:
Primer orden: Pre orden
se visita la raíz; se recorre el subárbol izquierdo; l bá b l i i d
se recorre el subárbol derecho;
se recorre el subárbol izquierdo; Segundo orden: Recorrida en orden se visita la raíz; Recorrida en‐orden se visita la raíz;
Orden simétrico
se recorre el subárbol derecho;
Tercer orden:
Post‐orden
d
Cursos de inducción a la MCC
se recorre el subárbol izquierdo; se recorre el subárbol derecho;
se recorre el subárbol derecho;
se visita la raíz;
Estructuras de datos
© Cinvestav‐Tamaulipas 2012 9
Ejemplo de recorridos en profundidad
A
B
D
C
E
F
G
Preorden: A, B, D, E, C, F, G
Inorden: D, B, E, A, F, C, G
Inorden: D B E A FC G
Postorden: D, E, B, F, G, C, A
Cursos de inducción a la MCC
Estructuras de datos
© Cinvestav‐Tamaulipas 2012 10
Grafos


Un grafo G es un par (V,E), tal que:
V: conjunto de nodos
E: conjunto de arcos conectando a los nodos en V
Un arco e = (u,v) es un par de nodos
a
b
c
d
V= {a,b,c,d,e}
V
{ b d }
E= {(a,b),(a,c),(a,d),
(b,e),(c,d),(c,e),
(d,e)}
b
c
V={a, b, c}
E={<a, b>,<a, c>, <c,b>}
e
Cursos de inducción a la MCC
a
Estructuras de datos
© Cinvestav‐Tamaulipas 2012 11
Grafos dirigidos y no dirigidos

Dirigido (o Digrafo)
 Cada
Cada línea tiene una dirección ea t e e u a d ecc ó
a su sucesor
 Note que <vi, vj> ≠ <vj, vi>

No dirigido
 Las líneas no tienen dirección
 Note <vi, vj> = <vj, vi>。
Note <vi vj> = <vj vi>。
Cursos de inducción a la MCC
Estructuras de datos
© Cinvestav‐Tamaulipas 2012 12
Operaciones en grafos

Considere un grafo G y dos nodos x y y





añade(G, x,y):
añade(G
x y): añade en G un arco de x a y,
y si no existe
borra(G, x,y): suprime un arco de x a y, si existe
adyacente(G,
y
( , x,y):
,y) verifica si hayy un arco de x a y en G
vecinos(G, x): lista todos los nodos y tal que hay un arco
entre x y y
En los grafos que tienen valores asociados a sus arcos,
también se tienen:
 asigna_valor(G,
i
l (G x,y,v):
) asigna
i
ell valor
l asociado
i d all arco (x,y)
( )a
v.
obtener valor(G, x,y): regresa el valor asociado al arco (x,y).
 obtener_valor(G,
Cursos de inducción a la MCC
Estructuras de datos
© Cinvestav‐Tamaulipas 2012 13
Referencias


Weiss, Mark A. Data Structures and Algorithm Analysis
in C++,
C++ 3rd Ed.
Ed Addison
Addison‐Wesley
Wesley, 2007.
2007
Joyanes Aguilar, Luis. Programación en C++:
Algoritmos, estructuras de datos y objetos. McGraw
Hill, 2000.
Cursos de inducción a la MCC
Estructuras de datos
© Cinvestav‐Tamaulipas 2012 14