Estructura de datos
description
Transcript of Estructura de datos
![Page 1: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/1.jpg)
![Page 2: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/2.jpg)
4.1 Árboles.4.1.1 Definición.4.1.2 Representación en memoria de árboles.
4.1.2.1 Árboles generales.4.1.2.2 Árboles binarios.
4.1.3 Recorridos en un árbol binario.4.1.3.1 Preorden.4.1.3.2 Inorden.4.1.3.3 Posorden.
4.1.4 Balanceo de árboles binarios.4.1.5 Clases para la implementación de árboles.
4.2 Grafos.4.2.1 Definición.4.2.2 Tipos de grafos.4.2.3 Representación de grafos en memoria.4.2.4 Clases para la implementación de grafos.
Unidad 4.- Estructuras no lineales.
![Page 3: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/3.jpg)
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.
Unidad 4. Estructuras no lineales.4.1 Árboles.
Definición
![Page 4: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/4.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Concepto de árbol 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.
![Page 5: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/5.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Concepto de árbol Un árbol se caracteriza por estar formado por
un conjunto finito de nodos, conectados por una serie de aristas, tales que verifican que:
hay un único nodo especial llamado raíz.
cada nodo, excepto la raíz, tiene un único nodo padre.
los nodos restantes se dividen en árboles mas pequeños llamados subárboles.
la definición de árbol implica tener una estructura recursiva (por la división en subárboles). la representación de los árboles se realiza con notaciones típicas de los árboles genealógicos. hay un único camino desde la raíz hasta cada nodo.
![Page 6: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/6.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
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. Ej.: los nodos encerrados en el triangulo
![Page 7: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/7.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
![Page 8: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/8.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
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.
![Page 9: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/9.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
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.
![Page 10: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/10.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
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
![Page 11: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/11.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
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.
![Page 12: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/12.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
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.
![Page 13: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/13.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
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.
![Page 14: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/14.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Ejemplo: expresiones aritméticas nodos internos: operadores. nodos hoja: operandos.
2(a – 1) + 3b
![Page 15: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/15.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
![Page 16: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/16.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Ejemplo:
![Page 17: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/17.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Implementación basada en enlaces
![Page 18: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/18.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Á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)
![Page 19: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/19.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Ejemplo:
![Page 20: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/20.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Ejemplo:
![Page 21: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/21.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
En algunos casos se exige que el árbol sea completo, es decir que todo nodo interno tenga sus dos descendientes.
![Page 22: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/22.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Operaciones:
Búsqueda.
Inserción.
Eliminación
![Page 23: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/23.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Búsqueda
![Page 24: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/24.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Búsqueda
![Page 25: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/25.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Inserción
![Page 26: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/26.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Inserción
![Page 27: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/27.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Ejemplo de Inserción
![Page 28: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/28.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Ejemplo de Inserción
![Page 29: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/29.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Eliminación
![Page 30: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/30.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Algoritmo para borrar un nodo de un árbol binario de búsqueda.
Para borrar un nodo con información X se presentan los siguientes casos.
1.- Que el nodo no exista: no se realiza ninguna acción.
2.- El nodo a eliminar tiene 0 o 1 hijo: El padre del nodo a eliminar (abuelo) toma como hijo al nodo nieto.
3.-El nodo a eliminar tiene 2 hijos: El nodo con la información X no se borra físicamente, se realiza una sustitución de información, (solo datos) con una de las siguientes acciones.
a) La información mayor del subárbol izquierdo.b) La información menor del subárbol derecho.c) Después de la sustitución el valor que sustituyo al nodo X se manda a eliminar partiendo del subárbol donde se encuentra.
![Page 31: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/31.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Eliminación
![Page 32: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/32.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Eliminación
![Page 33: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/33.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Árbol binario: operaciones del TAD
![Page 34: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/34.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Árboles Equilibrados
![Page 35: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/35.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Árboles Equilibrados
![Page 36: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/36.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Árboles Equilibrados
![Page 37: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/37.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Árboles Equilibrados
![Page 38: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/38.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Árboles Equilibrados
![Page 39: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/39.jpg)
Unidad 4. Estructuras no lineales.4.1 Árboles.
Árboles Equilibrados
![Page 40: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/40.jpg)
Introducción• Los grafos sirven para representar relaciones
arbitrarias (no necesariamente jerárquicas) entre objetos de datos
PLAZA DECASTILLA
NUEVOSMINISTERIOS
GREGORIOMARAÑÓN
CANAL
GUZMAN EL BUENO
CUATROCAMINOS
AVDA. DEAMÉRICA
Unidad 4. Estructuras no lineales.4.2 Grafos.
![Page 41: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/41.jpg)
juan
davidpablo
uc3m.es
otro.net
inf.uc3m.es
rediris.nettelefonica.net
it.uc3m.es
Lab-a02lab-a01
Introducción: aplicaciones• Circuitos electrónicos
– Tarjetas impresas– Circuitos integrados
• Redes de transporte– Autopistas– Vuelos
• Redes de ordenadores– LANs– Internet– Web
• Bases de datos– Diagramas
entidad/relación
Unidad 4. Estructuras no lineales.4.2 Grafos.
![Page 42: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/42.jpg)
Fundamentos: 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.
• Un arco tiene, a veces, asociado un factor de peso, en cuyo caso se dice que es un grafo valorado.
Unidad 4. Estructuras no lineales.4.2 Grafos.
![Page 43: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/43.jpg)
Fundamentos: grafos dirigidos
Grafo no dirigido
V(G1) = {a,b,c,d}
A(G1) = {(a,b),(a,d),(b,c),(b,d)}
Grafo dirigidoV(G2) = {1,3,5,7,9}A(G2) = {(1,3),(3,1),(9,1),
(3,5),(5,7)}
a
b
d
c
1
3
5
7
9
Unidad 4. Estructuras no lineales.4.2 Grafos.
![Page 44: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/44.jpg)
Fundamentos• Grado de un nodo
– En un grafo 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 conexografo no conexo con dos componentes conexas
Unidad 4. Estructuras no lineales.4.2 Grafos.
![Page 45: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/45.jpg)
Fundamentos: camino• Un camino P de longitud n en
el grafo G desde u0 a un es la secuencia de n+1 vértices P = (u0, u1, ..., un) tal que (ui,ui+1) son arcos de G para 0 i n
• Un camino es simple si todos los nodos que forman el camino son distintos, pudiendo ser iguales los extremos del camino
• Ejemplo:
– P1 es simple
– P2 no es simple
P1
XU
V
W
Z
Y
a
c
b
e
d
f
g
hP2
Unidad 4. Estructuras no lineales.4.2 Grafos.
![Page 46: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/46.jpg)
Fundamentos: ciclos y bucles• Un ciclo es un camino
simple cerrado con u0=un, compuesto al menos por tres nodos
• Un ciclo es simple si todos sus vértices y arcos son distintos
• Un arco que va desde un vértice a sí mismo (u,u) se denomina bucle
• Ejemplo
– C1 es un ciclo simple
– C2 es un ciclo no simple
C1
XU
V
W
Z
Y
a
c
b
e
d
f
g
hC2
Unidad 4. Estructuras no lineales.4.2 Grafos.
![Page 47: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/47.jpg)
TAD GRAFO
• Composición:
<grafo> :: = {<vertice>} + {<arista>}<vertice> ::= <<refVertice>> + [<<info>>]<arista> ::= <<refVertice>> + <<refVertice>>
<grafoEtiquetado> :: = {<vertice>} + {<aristaEtiquetada>}<vertice> ::= <<refVertice>> + [<<info>>]<aristaEtiquetada> ::= <<refVertice>> + <<refVertice>>
+ <<etiqueta>>
Unidad 4. Estructuras no lineales.4.2 Grafos.
![Page 48: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/48.jpg)
TAD GRAFO: Operaciones
recorrer(grafo,tipoRecorrido)Recorrido del grafo
borrarArista(grafo,arista)
borrarVertice(grafo, referenciaVertice) Eliminación de vértices
insertarVertice(grafo, vertice)
crearGrafo (grafo)Creación del grafoInclusión de vértices
Borrar aristas
insertarArista(grafo, vertice1, vertice2)Inclusión de aristas
Unidad 4. Estructuras no lineales.4.2 Grafos.
![Page 49: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/49.jpg)
TAD GRAFO: Operaciones
asignarInfo(referenciaVertice, valorInformacion)Modificación de vertices
info(referenciaVertice) Informacion
grado(referenciaVertice) Entero
gradoEntrante(referenciaVertice) Entero
gradoSaliente(referenciaVertice) Entero
adyacentes(referenciaVertice) {referenciaVertice}
incidentes{referenciaVertice) {referenciaVertice}
esAdyacente(refenciaVertice1, referenciaVertice2) Boolean
Acceso a los vertices
asignarEtiqueta(referenciaArista, valorEtiqueta)
Modificación de aristas
vertices(referenciaArista) (refVertice, refVertice)
destino(referenciaArista) refVertice
origen(referenciaArista) refVertice
etiqueta((referenciaArista) etiqueta
Acceso a las aristas
Unidad 4. Estructuras no lineales.4.2 Grafos.
![Page 50: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/50.jpg)
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
Unidad 4. Estructuras no lineales.4.2 Grafos.
![Page 51: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/51.jpg)
Representación: matriz de adyacencia
2
1
4
3
2
3
5
4
1
0 1 1 11 0 0 11 0 0 01 1 0 0
0 1 0 0 00 0 1 0 00 1 0 0 10 0 0 0 00 0 0 1 0
2
3
5
4
1
1
2
6
2
1
0 1 0 0 00 0 2 0 00 6 0 0 20 0 0 0 00 0 0 1 0
Unidad 4. Estructuras no lineales.4.2 Grafos.
![Page 52: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/52.jpg)
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
Unidad 4. Estructuras no lineales.4.2 Grafos.
![Page 53: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/53.jpg)
Representación: listas de adyacencia
• Ejemplo
1
3
2
5
4
1
2
5
4
3
3 4
3
1
1 2 4
Unidad 4. Estructuras no lineales.4.2 Grafos.
![Page 54: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/54.jpg)
Recorridos
• Primero en profundidad
– Visitar vértice inicial vi
– Visitar vértice adyacente a vi
... proceder así hasta encontrar uno ya visitado...
– Volver atrás hasta llegar a un vértice con adyacentes sin visitar
– El recorrido termina cuando volviendo atrás llegamos al vértice innicial vi y no quedan adyacentes por recorrer
• Primero en anchura– Visitar vértice inicial vi
– Visitar todos los vértices adyacentes a vi
– Al terminar, comenzar a visitar los adyacentes a los adyacentes a vi
... proceder así hasta que no queden vértices por visitar
Unidad 4. Estructuras no lineales.4.2 Grafos.
![Page 55: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/55.jpg)
Recorridos• Profundidad
RPP(vi)
{
marcar vi como visitado
para cada vk adyacente a v
si vk no visitado
entonces RPP(vk)
}
• AnchuraRPA(vi)
{
marcar vi como visitado
meter vi en cola q
mientras cola q no vacía
sacar v de cola q
para cada vk adyacente a v
si vk no visitado
entonces
marcar vk visitado
meter vk en cola q
}
Unidad 4. Estructuras no lineales.4.2 Grafos.
![Page 56: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/56.jpg)
Recorridos: operaciones auxiliares
• Marcar vértice como visitado– Si los vértices están identificados por algún tipo ordinal,
emplear un conjunto que contenga los identificadores de los vértices visitados
• Encontrar los vértices adyacentes– Con matrices de adyacencia: recorrer la fila
correspondiente al vértice, buscando columnas a TRUE– Con listas de adyacencia: recorrer la lista
• Cola de vértices visitados en anchura– Operaciones del TAD Cola
Unidad 4. Estructuras no lineales.4.2 Grafos.
![Page 57: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/57.jpg)
Recorrido primero en profundidad
1, 3, 6, 10, 13, 12, 9, 5, 2, 4, 7, 8, 11
1
2
3
4
6
7
8
5
10
11
9
13
12
1
10
2
11
6
8
3
9
7
4
5
12
Unidad 4. Estructuras no lineales.4.2 Grafos.
![Page 58: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/58.jpg)
Recorrido primero en profundidad
0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 01 0 0 1 0 1 1 0 0 0 0 0 01 1 1 0 0 1 1 1 0 0 0 0 00 1 0 0 0 0 0 1 1 0 0 0 00 0 1 1 0 0 0 0 0 1 0 0 00 0 1 1 0 0 0 0 0 1 0 0 00 0 0 1 1 0 0 0 0 0 1 0 00 0 0 0 1 0 0 0 0 0 1 1 00 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 10 0 0 0 0 0 0 0 1 0 0 0 10 0 0 0 0 0 0 0 0 1 1 1 0
12436
107
11859
1213
123456789
10111213
1 2 3 4 5 6 7 8 9 10 11 12 13
Unidad 4. Estructuras no lineales.4.2 Grafos.
![Page 59: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/59.jpg)
Recorrido primero en anchura
1
2
3
4
6
7
8
5
10
11
9
13
12
1
2
3
4
5
6
7
8
9
10
11
12
1, 3, 4, 2, 6, 7, 8, 5, 10, 11, 9, 13, 12
Unidad 4. Estructuras no lineales.4.2 Grafos.
![Page 60: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/60.jpg)
Recorrido primero en anchura
0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 01 0 0 1 0 1 1 0 0 0 0 0 01 1 1 0 0 1 1 1 0 0 0 0 00 1 0 0 0 0 0 1 1 0 0 0 00 0 1 1 0 0 0 0 0 1 0 0 00 0 1 1 0 0 0 0 0 1 0 0 00 0 0 1 1 0 0 0 0 0 1 0 00 0 0 0 1 0 0 0 0 0 1 1 00 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 10 0 0 0 0 0 0 0 1 0 0 0 10 0 0 0 0 0 0 0 0 1 1 1 0
123456789
10111213
123456789
10111213
1 2 3 4 5 6 7 8 9 10 11 12 13
Unidad 4. Estructuras no lineales.4.2 Grafos.
![Page 61: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/61.jpg)
Árbol reducido/de expansión
• Un árbol puede verse como un caso particular de un grafo: un grafo conexo acíclico
• Para obtener el árbol reducido de un grafo hay que eliminar todas las aristas que producen ciclos, pero manteniéndolo conexo– Aplicación: encaminamiento en
redes de comunicaciones• No existe un único árbol reducido de
un grafo, pues dependerá del nodo de partida y de la forma de recorrerlo
• Cuando el grafo es valorado, puede calcularse el árbol de expansión de coste mínimo
grafo
Árbol de expansión
Unidad 4. Estructuras no lineales.4.2 Grafos.
![Page 62: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/62.jpg)
Árbol reducido (anchura)
1
2
3
4
6
7
8
5
10
11
9
13
12
Unidad 4. Estructuras no lineales.4.2 Grafos.
![Page 63: Estructura de datos](https://reader035.fdocumento.com/reader035/viewer/2022062217/56813de4550346895da7bb4f/html5/thumbnails/63.jpg)
Árbol reducido (profundidad)
1
2
3
4
6
7
8
5
10
11
9
13
12
Unidad 4. Estructuras no lineales.4.2 Grafos.