Estructura de Datos
Parte - 3
Lic. Ivan Fernandez Daza
1
AGENDA DE HOY
• Pautas sobre el trabajo de investigacion.
• Introduccion a Estructuras de Datos No Lineales.
• Clasificacion de Estructuras de Datos No Lineales.
• Arboles:
✓ Definicion.
✓ Caracteristicas y aplicaciones.
✓ Terminologia basica.
✓ Recorridos en arboles.
✓ Arboles binarios de busqueda.
✓ Operaciones basicas en arboles
▪ Propuesta de ejercicios.
2
Trabajo Final de Investigacion
Requisitos de la entrega del documento de investigacion:
• En el documento de investigacion NO solo debe haber texto,
sino que tambien debe haber imagenes, graficos, tablas.
• El documento de investigacion este en formato APA.
• El numero de hojas minimo del documento de investigacion
es de 15 hojas.
• El trabajo de investigacion debera ser realizado en forma
individual.
NOTA: El documento de investigacion debe ser subido a la
Plataforma UDABOL en formato PDF.
Fecha de entrega: jueves 24 de noviembre
Trabajo Final de Investigacion
Se pide realizar una investigacion sobre el tema “Grafos una estructura
de datos no lineal”. Todo el trabajo bajo el formato APA.
Se sugieren algunos puntos del trabajo:
• Definicion grafo
• Ejemplos de aplicaciones en el mundo real.
• Tipos de grafos.
• Otras definiciones: Grado de un nodo, etc.
• Grafos conexos.
• Operaciones sobre grafos: buscar, eliminar, insertar, etc
• Representacion de un grafo: Matriz de adyacencias, Lista de
adyacencias
• Camino de un grafo.
• Ciclos y bucles en un grafo.
• Recorridos en un grafo: Primero en profundidad, primero en anchura.
• Grafo Reducido.
• Grafo de expansion.
• Programas en Java de grafos.
Trabajo Final de Investigacion
Requisitos de la entrega del documento de investigacion:
• En el documento de investigacion NO solo debe haber texto,
sino que tambien debe haber imagenes, graficos, tablas.
• El documento de investigacion este en formato APA.
• El numero de hojas minimo del documento de investigacion
es de 15 hojas.
• El trabajo de investigacion debera ser realizado en forma
individual.
NOTA: El documento de investigacion debe ser subido a la
Plataforma UDABOL en formato PDF.
Estructura de datos no lineales
Definicion:
Cada elemento o NODO puede estar enlazado a
cualquier otro componentes, es decir un elemento
puede tener mas de un sucesor o antecesor.
Se trata de estructuras de datos en las que cada
elemento puede tener varios sucesores y/o varios
antecesores.
A estas estructuras se les llama también estructuras
de datos multi-enlazadas.
6
Tipos de Estructuras de datos no
lineales
ARBOL:
7
Tipos de Estructuras de datos no
lineales
GRAFO:
2
1 3 6 3
10
1 7
10 4
4
11 12 11
9 13
8
5
2 8
5 7 8
6 12
9
Arboles
Definicion:Un árbol es una colección de elementos,
llamados nodos, uno de los cuales se distingue con
el nombre de raíz, los cuales mantienen una
relación (parentezco) que define una estructura
jerárquica entre ellos.
• Estructura Jerárquica no lineal, dinámica.
• Relaciones padre-hijo entre nodos.
• Ejemplos: sistema de archivos, estructura
de un libro, diagrama organizacional,
árboles genealógicos, etc. 9
Terminología básica
❑ Raíz: único nodo sin padre. Ej.: nodo A
❑ Nodo interno: tiene al menos un hijo. Ej.: nodos B, F, C
❑ Nodo hoja (externo): nodo sin hijos. Ej.: nodos E, I, J,
K, G, H, D
❑ Descendiente directo: hijo.
Ej.: B es descendiente directo de A
❑ Descendiente: hijo, nieto, etc…
Ej.: I es descendiente de F, B y A
❑ Subárbol: árbol formado por
un nodo y sus descendientes. 1
Ej.: los nodos encerrados en 0
el triangulo
Terminología básica
❑ Grado de un nodo: Num. de descendientes directos.
Ej.: el nodo B es grado 2.
❑ Grado de un árbol: el grado mayor de sus nodos. Ej.: el
nodo A y F son los de mayor grado (3), por lo tanto el
árbol es grado 3.
❑ Árbol binario: árbol de grado 2,
cada nodo tiene como mucho dos
descendientes directos.
❑ Árbol multicamino: árbol de
grado mayor que 2, cada nodo
puede tener n descendientes
directos.
Terminología básica
❑ Profundidad de un nodo: Num. de predecesores. Ej.:
profundidad de A es 0, profundidad de H es 2.
❑ Altura del árbol: es igual a la profundidad de su nodo
mas profundo + 1. Ej.: la profundidad de I, J y K que son
los nodos mas profundos es 3 por lo tanto la altura de
árbol es 3 + 1 = 4.
Terminología básica
❑ Camino: existe un camino del nodo X al nodo Y, si
existe una sucesión de nodos que permita llegar desde X
hasta Y, su longitud es el número de aristas que lo
conforman.
camino(A,K)= {A, B, F, K}
longitud 3
camino(C,K)= {} no hay camino
Recorrido Preorden
❑ Se visita primero la raíz, luego el subárbol
izquierdo y por ultimo el subárbol derecho, esto de
manera recursiva para cada subárbol partiendo de la
raíz.
Recorrido Inorden
❑ Se visita primero el subárbol izquierdo, luego la
raíz y por ultimo el subárbol derecho, esto de manera
recursiva para cada subárbol partiendo de la raíz.
Recorrido Postorden
❑ Se visita primero el subárbol izquierdo luego el
subárbol derecho y por ultimo la raíz, esto de
manera recursiva para cada subárbol partiendo de la
raíz.
Ejemplo de Recorridos en un arbol
R-I-D
I-R-D
I-D-R
Recorrido por Amplitud: 104, 71, 240, 17, 19, 108, 245, 3, 18, 110
Árboles Binarios de Búsqueda
❑ Un árbol binario de búsqueda es un árbol
binario en el que para cada nodo n,
➢ todas las claves de los nodos del subárbol
izquierdo son menores que la clave de n (o
igual).
➢ y todas las del subárbol derecho mayores
(o igual)
Ejemplo:
Operaciones:
❖ Búsqueda.
❖ Inserción.
❖ Eliminación
Busqueda
Inserción
Inserción
Eliminación
Árbol binario: operaciones del TAD
Árboles Equilibrados
Árboles Equilibrados
AGENDA DE HOY
• Introduccion a estructura de datos no lineal Grafos.
• Revision de la “Practica de Grafos”.
2
6
Grafos
Los grafos sirven para representar relaciones
arbitrarias (no necesariamente jerárquicas) entre
objetos de datos.
PLAZA DE
CASTILLA
GUZMAN
EL BUENO
NUEVOS
CUATRO MINISTERIOS
CAMINOS
AVDA. DE
AMÉRICA
CANAL GREGORIO
MARAÑÓN
Grafos-aplicaciones
Circuitos electrónicos
Tarjetas impresas lab-a01 Lab-a02
Circuitos integrados [Link]
Redes de transporte
Autopistas [Link]
Vuelos
Redes de ordenadores [Link]
[Link]
LANs [Link]
Internet
Web
[Link]
Bases de datos juan
Diagramas pablo
david
entidad/relación
Grafos
Definiciones:
• Un grafo consiste en un conjunto de vértices o nodos y
un conjunto de arcos. Se representa con el par G = (V,A).
• Un arco o arista está formado por un par de nodos u y v, y
se representa por (u,v)
• Un grafo es dirigido si los pares de nodos que forman los
arcos son ordenados y se representan u → v. Un grafo no
dirigido es aquel que los arcos están formados por pares
de nodos no ordenados, se representa u − v.
• Si (u,v) es una arista en A(G), entonces u y v se dice que
son vértices adyacentes.
Grafos b
Grafo no dirigido
V(G1) = {a,b,c,d} d
A(G1) = {(a,b),(a,d),(b,c),(b,d)}
a
c
3
Grafo dirigido
9
V(G2) = {1,3,5,7,9} 5
A(G2) = {(1,3),(3,1),(9,1),
(3,5),(5,7)}
1
7
Fundamentos
Grado de un nodo
En un grafo No dirigido
Grado de un nodo u = nº de aristas que contienen a u
En un grafo dirigido
Grado de entrada de u = nº de arcos que llegan a u
Grado de salida de u = nº de arcos que salen de u
Grafos conexos
Un grafo no dirigido es conexo si existe un camino entre
cualquier par de nodos que forman el grafo
Ejemplos:
grafo no conexo con dos
grafo conexo componentes conexas
TAD GRAFO: Operaciones
Creación del grafo crearGrafo (grafo)
Inclusión de vértices insertarVertice(grafo, vertice)
Eliminación de vértices borrarVertice(grafo, referenciaVertice)
Inclusión de aristas insertarArista(grafo, vertice1, vertice2)
Borrar aristas borrarArista(grafo,arista)
Recorrido del grafo recorrer(grafo,tipoRecorrido)
Representación: matriz de adyacencia
Matriz de adyacencias
Sea G = (V,A) un grafo de n nodos, suponemos que los
nodos V = {u1,...,un} están ordenados y podemos
representarlos por sus ordinales {1,2,...,n}.
La representación de los arcos se hace con una matriz A
de nxn elementos aij definida:
1 si hay arco (ui,uj)
aij
0 si no hay arco (ui,uj)
Optimización
Usar la diagonal principal de la matriz de adyacencia para
representar la existencia de un vértice
Representación: matriz de adyacencia
3 1 3 2
1 1 2
5 4 5
1 6
2 2 2 1
4 3 4
1 2 3 4 5
1 0 1 0 0 0 0 1 0 0 0
0 1 1 1
2 0 0 1 0 0 0 0 2 0 0
1 0 0 1
3 0 1 0 0 1 0 6 0 0 2
1 0 0 0
4 0 0 0 0 0 0 0 0 0 0
1 1 0 0
5 0 0 0 1 0 0 0 0 1 0
Representación
Matriz de adyacencia
Poco eficiente si el nº de vértices varía a lo largo del
tiempo de vida del grafo
Puede darse el caso de que el nº de vértices sea mayor
del previsto inicialmente
Poco eficiente cuando el grafo tiene pocos arcos (la
matriz es “dispersa”)
Listas de adyacencia
Representar una lista de todos los vértices
Cada objeto vértice guarda una lista de adyacencia con
un objeto arista para cada vértice alcanzable desde él
Representación: listas de adyacencia
Ejemplo 1 3 4
3 2 3
2
3 1
1
5 4
4 5 1 2 4
Aplicación de Grafos en la vida real
Método de la fuerza bruta
El método de la fuerza bruta no implica la aplicación de ningún algoritmo
sistemático, tan solo consiste en explorar todos los recorridos posibles.
Recorridos en Grafos
Recorrido en Anchura
• El recorrido de búsqueda en anchura, en amplitud o
expansión, es una estrategia aplicable indistintamente al
caso de grafos dirigidos y no dirigidos. El recorrido en
anchura es una generalización del recorrido por niveles de
un árbol.
• Se trata de visitar un nodo inicial y luego a todos los nodos
que están a un arco de distancia de éste, luego a todos los
nodos que están a dos arcos de distancia de éste y así
sucesivamente, hasta alcanzar a todos los nodos a los que
se pueda llegar desde el nodo inicial.
Recorridos en Grafos
Recorrido en Anchura
Para el siguiente grafo, habría varios recorridos en anchura posibles,
entre los cuales podríamos mencionar:
Visitando primero el nodo izquierdo seria:
A→B→D→C→E
Visitando primero el derecho seria:
A→D→B→E→C
Recorridos en Grafos
Recorrido en Profundidad
La estrategia de recorrido en profundidad es la siguiente:
1. Se toma un nodo “s” como comienzo, y se marca.
2. A continuación se toma y se marca un nodo no marcado adyacente a
“s”, y ese nodo pasa a ser el nuevo nodo de partida, dejando
posiblemente por el momento al nodo inicial original con nodos no
explorados.
3. La búsqueda continúa por el grafo hasta que el camino en curso
finalice con un grafo de salida igual a cero, o bien en un nodo en que
todos los nodos adyacentes estén marcados.
4. A continuación la búsqueda vuelve al último nodo que todavía tenga
nodos adyacentes sin marcar, y continúa marcando todos los nodos
de forma recursiva hasta que ya no queden nodos sin marcar.
Recorridos en Grafos
Recorrido en Profundidad
Para el siguiente grafo, habría varios recorridos en profundidad posibles,
entre los cuales podríamos mencionar:
Visitando primero el nodo izquierdo seria:
A→B→C→E→D
Visitando primero el nodo derecho seria:
A→D→E→B→C
AGENDA DE HOY
Problemas propuestos de Grafos:
• Problema de representar un mapa de Bolivia con
un grafo.
• Problema de coloracion de un Grafo de Bolivia.
• Problema de coloracion de un Grafo.
• Problema de carreteras entre ciudades.
