1 Unidad de Aprendizaje ESTRUCTURAS DE DATOS Tema: Ordenamiento y grafos Mtro. Yaroslaf Aarón Albarrán Fernández Ingeniería en Sistemas Inteligentes Universidad Autónoma del Estado de México Unidad Académica Profesional Nezahualcóyotl

2 DIRECTORIO DE LA UAEM Dr. en D. Jorge Olvera García Rector Dr. en Ed. Alfredo Barrera Baca Secretario de Docencia Dra. en Est. Lat. Ángeles Ma. del Rosario Pérez Bernal Secretaria de Investigación y Estudios Avanzados Dr. en D. José Benjamín Bernal Suárez Secretario de Rectoría Mtra. en E. P. D. Ivett Tinoco García Secretaria de Difusión Cultural Mtro. en C. I. Ricardo Joya Cepeda Secretario de Extensión Vinculación Mtro. en E. Javier González Martínez Secretario de Administración Dr. en C. Pol. Manuel Hernández Luna Secretario de Planeación y Desarrollo Institucional Mtra. en A. Ed. Yolanda E. Ballesteros Sentíes Secretaria de Cooperación Internacional Dr. en. D Hiram Raúl Piña Libien Abogado General Lic. en Com. Juan Portilla Estrada Director General de Comunicación Universitaria Lic. Jorge Bernaldez García Secretario Técnico de la Rectoría Mtro. en A. Emilio Tovar Pérez Director General de Centros Universitarios y Unidades Académicas Profesionales Mtro. en A. Ignacio Gutiérrez Padilla Contralor DIRECTORIO DE LA UAP- NEZAHUALCÓYOTL Dr. en C.E. Luis Ramón López Gutiérrez Coordinador Dr. en F.M. Israel Gutiérrez González Subdirector Académico Lic. en E. Alfredo Ríos Flores Subdirector Administrativo Dra. en C. S. María Luisa Quintero Soto Coordinadora de Investigación y Estudios Avanzados Lic. en A. E. Víctor Manuel Durán López Coordinador de Planeación y Desarrollo Institucional Dr. en E. Selene Jiménez Bautista Coordinadora de la Licenciatura en Comercio Internacional Dra. en C. Georgina Contreras Landgrave Coordinadora de la Licenciatura en Educación para la Salud Dra. en C. Dora María Calderón Nepamuceno Coordinadora de Ingeniería en Sistemas Inteligentes Mtro. en C. Juan Antonio Jiménez García Coordinador de Ingeniería en Transporte

3 Ubicación de la asignatura de Algoritmos Genéticos dentro del programa de la Lic. en Ingeniería en Sistemas Inteligentes

4 Programas de estudios por competencias en la Lic. en Ingeniería en Sistemas Inteligentes Espacio académico: UNIDAD ACADÉMICA PROFESIONAL NEZAHUALCÓYOTL Programa educativo: INGENIERÍA EN SISTEMAS INTELIGENTES Área de docencia: INGENIERÍA Y TECNOLOGÍA Aprobación de los HH Consejos Académico y de Gobierno Fecha de actualización: Programa elaborado por: M. EN C. MARÍA DEL CARMEN CEDILLO CHAGOYA M. EN C. JOSÉ ANTONIO CUEVAS BARRÓN ING. LUISA ALEJANDRA PUEBLA URBINA Nombre de la unidad de aprendizaje: ESTRUCTURA DE DATOS Fecha de elaboración: JULIO 2014 Clave Horas de Teoría Horas de Práctica Total de horas Créditos Tipo de unidad de aprendizaje Carácter de la unidad de aprendizaje Núcleo de formación Modalidad L40630 3.02.05.08.0CURSOOBLIGATORIASUSTANTIVO PROFESIONAL PRESENCIAL Prerrequisitos (Conocimientos previos): - CONOCIMIENTOS BÁSICOS DE PROGRAMACIÓN - CONOCIMIENTOS SOBRE LA PROGRAMACIÓN ORIENTADA A OBJETOS Unidad de aprendizaje antecedente: PROGRAMACIÓN ORIENTADA A OBJETOS Unidad de aprendizaje consecuente: ORGANIZACIÓN DE ARCHIVOS Programas en los que se imparte: UAPS: Atlacomulco, Ecatepec, Texcoco, Valle de Chalco, Valle de México, Valle de Teotihuacán, Valle de Zumpango.

5 ESTRUCTURAS DE DATOS Objetivos  Identificar, seleccionar y aplicar eficientemente tipos de datos abstractos, métodos de ordenamiento y búsqueda para la optimización del rendimiento de soluciones de problemas del mundo real.

6 Estructuras de Datos. Unidad I 1. Ordenación por el Mínimo 2. Variables 3. Pseudocódigo 4. Ordenación por selección 5. Ordenación Shell 6. Métodos de búsqueda 6.1.Búsqueda Binaria 7. Grafos 7.1. Orden de un Grafo 7.2. Orden de un Grafo 7.3. Grafo a Cíclico 8. Etiquetamiento Consistente 9. Grafo Completo 10. Matriz de Adyacencias de un Grafo 11. Lista de Adyacencias 12. Subgrafos

7 1. Ordenación por el Mínimo PRIMERA ETAPA: Se considera que la posición de l mínimo es el que primera recorrer lista desde la segunda para encontrar la posición del mínimo en el caso de que no sea elemento situado en la primera posición intercambiar las de tal manera u que el mínimo ocupa la primera posición SEGUNDA ETAPA: El íntimo ocupa la segunda posición recorreremos la lista desde la tercera posición buscamos el mínimo y lo intercambia con el elemento de la segunda posición en caso de que no ocupe dicho lugar de tal forma de que el segundo elemento más pequeño de toda la lista este situada en la segunda posición así sucesivamente hasta n-1 etapas pues su los n-1 primeros elementos están ordenados el ultimo el n también lo estará

8 2. Variables L=nombre de la lista. N=numero de electos de la lista l. Aux=para realizar el intercambio de los elementos. i=contador de etapas desde 1 hasta n-1. J=recorre la lista desde etapa +1,i+1 hasta n para encontrar el mínimo. Posmin= guardar la posición l mínimo coinciden con el número de etapa.

9 3. Pseudocódigo i=1 se considera que el mínimo ocupa la 1 posición hacer mientras i

10 las comparaciones empiezan desde la posición siguiente compráramos y vamos guardando la posición del mínimo en posmin. al terminar las comparaciones de cada etapa será cuando se realiza el intercambio de elementos. se aumenta el contador de las etapas el mínimo pasa a ser el elemento situado en la posición i-esima posmin=1. las comparaciones empiezan en j=i+1 el siguiente elemento al final de todas la etapas lista ordenada.

11 4. Ordenación por selección Ordenar un arreglo de enteros en orden ascendente A[0] deberá tener el valor más pequeño as hasta A [ n-1] sucesivas interacciones que intercambian el elemento más pequeño sucesivamente con el primer elemento de la lista A[0] en la primera iteración se busca el elemento más pequeño de la lista y se intercambia con A[0] después de la primera iteración el frente de la lista esta ordenado y el resto no A[],A[2].......A[n-1] busca en la siguiente iteración el más pequeño y lo intercambia con A[0] y A[1] ordenados y así sucesivamente hasta que este ordenado

12 51 21 39 80 36---- seleccionar 21 intercambiar 21 y A[0] 21 51 39 80 36---- seleccionar 36 intercambiar 36 con A[1] 21 36 39 80 51---- seleccionar 39 intercambiar 39 con [2] 21 36 39 80 51---- seleccionar 51 intercambia 51 con. AQ[3] 21 36 39 51 80---- lista ordenado pasos: seleccionar el elemento. más pequeño de la lista a intercambiar lo con el primer elemento A[0] ahora el valor más pequeño esta en la primera posición del vector

13 5. Ordenación Shell También denominado ordenamiento por inserción con incrementos decrecientes recordando que el algoritmo de cada elemento continuos de su izquierda uno tras otro si el elemento a insertar es l más pequeño hay que realizar muchas comparaciones antes de colocarlas en el lugar definido. El algoritmo de shell modifica los saltos contiguos resultantes de las comparaciones por saltos de mayor tamaño y Con ello se no sigue que la ordenación sea más rápido se toma como salto inicial n/r (siendo n el número de elementos ) luego se reduce el salto a la mitad en cada repetición hasta que el salto es de tamaño 1 ejemplo: 6 -1- 5- 2- 3- 4- 0 7 elementos el salto inicial

14 6. Métodos de búsqueda Consiste en saber si un determinado elementos esta en la lista y en caso se hallarse indicara la posición que ocupara búsqueda lineal (secuencial) 1)valido para arreglos ordenados o desordenados 2) proceso de determinar si un elemento o su posición cumple una condición comparando con cada uno de los elementos en forma secuencial 3) se refiere para arreglos desordenados, datos de entrada, arreglo de varias dimensiones y la condición el valor a buscar proceso. 1) puede se que el valor no este en el arreglo 2) recorrer el arreglo hasta encontrar no el valor recorre uno por uno los elementos del arreglo hasta encontrarlo o no el elemento e indica si lo encontró la posición si no indica no esta el valor.

15 6.1.Búsqueda Binaria exclusiva de arreglos ordenados el método se basa en el conocimiento de la información sobre la cual se va a buscar entradas: el arreglo este ordenado dimensión del arreglo la condición el valor a buscar proceso 1) determinar la posición meolia del arreglo 2) mientras el elemento en la posición media =\ valor buscando ejecutar: 2.1 descartar una mitad del arreglo 2.2 determinar el nuevo como otra mitad 2.3 determinar el punto medio del nuevo rango 3) determina si se encuentra o no el valor 4) no encuentra el valor-+n búsqueda 5) no encuentra el valor - fin búsquedas

16 Ejemplo Buscar valor=75 Iteracion(1) 1 11 21 25 26 33 38 40 42 48 50 56 59 60 Ejemplo A(m) =59 Buscar valor 31 Iteracion descarta la segunda mitad 1 9 18 21 25 30 36 40 51 58 60 71 i=1 m=7 j=13 Iteracion (2) 1 9 18 21 25 30 36 i=1 m=4 j=7} se descarta la primera mitad Iteracion(3) 21 25 30 36 i=4 m=6 j=7 } se descarta la primera mitad Iteracion (4) 30 36 i=6 m=7 j=7} se descarta la primera mitad Iteracion(5) 36 40 M=7 j=7 i=8} termina la búsqueda del valor no se encuentra en posición m;i>j

17 7. Grafos Un grafo 6 consta de un conjunto de vértices o nodos v y un conjunto de arcos A cada uno de los cuales une un vértice con otro 6=(v,a)=(n,a) aristas de grafo. son arcos que unen los nodos. vi,vj. donde los elementos son las nodos que unen el arco grafo dirigido si en un grafo los arcos tienen una dirección el grafo se llama dirigido u orientado vi,vj. va de vi hasta vj, vj es adyacente a vi. también conocido como dígrafo grafo no dirigido. los arcos del grafo no indican una dirección no importa el orden es decir (vi,vj)=(vj,vi) los nodos de un grafo se pueden usar para representar los objetos y los arcos representan relaciones entre estos objetos grafo etiquetado. nodos y arcos de un grado tienen nombres y valores

18 7.1. Orden de un Grafo El número de nodos de un grafo se llama orden del grafo y se denota como Ord(g) = in (g) I=n el número de anotas o arcos es Ia( g) I= A talla de G =e(R) grafo de un vértice. El grafo de un vértice x es el número de vértices adyacentes a el esto es el número de arcos incidentes a x y se denota grad(x) relación entre arista y el orden de vértices Teorema1 si N(G)=x1,x2..........xn entonces grad (x1)+......+grad(xn)=2A donde A es el número de aristas incidentes

19 7.1. Orden de un Grafo trayectoria: una trayectoria T en un grafo es una secuencia de nodos v1,v2 tal que (v1,v2),(v2,v3) son arcos nota: cuando el grafo no tiene valora asociados a sus arcos la longitud de la trayectoria es el nuestro de arcos que la componen 1 2 34 5 La secuencia 1-2-4 es una Trayectoria de longitud 2 La secuencia 1-3-5-2-4 es un Trayectoria de longitud 4

20 7.2. Orden de un Grafo nota cuando los vértices de una trayectoria son todos =/ excepto el primero y el último.trayectoria simple trayectoria que comienza y termina en le mismo nodo. ciclo o circuito ciclos de longitud 1 se llaman bucles o lazos por que salen de uno nodo e inciden en el mismo modo sin pasar por ningún otra trayectoria simple. cuando los vértices de un trayectoria excepto posiblemente el primero y el último.

21 Ejemplo a b c de Trayectoria b-c-d-b es un ciclo y a la ves una trayectoria simple o bien mediante arcos o bien mediante de nodos

22 7.3. Grafo a Cíclico un grafo G es a cíclico si no contiene ciclos los grafos a cíclicos son usados para modelar situaciones de conjuntos de tarea que necesitan tener una secuencia particular y donde es importante que no existan ciclos puesto que una tarea en un ciclo estaría precedida e si misma es decir que se repetiría ejemplo. lista parcial para construir una cosa para cada tarea T la segunda cada una muestra aquellas arcos que deben ser completados antes que T pueda ser comenzada construir un diagrama para mostrar la relación entre las tareas

23 tarea hacer cimientos------1 adicionar el piso basé---1 hacer columnas---2y3 levantar paredes y techo----4 adicionar ciclo rasó-----4 instalar plomería-------4y5 instalar redes eléctricas-----4y6 pegar piso----4y8 instalar puertas pintar paredes interiores----4,7,8,9y9 pulir piso -----10

24 12 357 46 8 9 10 11 Diagrama a cíclico de tareas

25 8. Etiquetamiento Consistente forma de numerar los nodos de manera tal que cada nodo tenga un número más baja que cualquier nodo que el precederá def. sea g=(n,a) un digrafo sea {n1,n2.....nn} un etiqueta miento de los nodos el etiqueta miento es consistente si (ni,nj) ea-i

26 9. Grafo Completo es aquel en el que cada por de nodos distintos están unidos por un arco o cualquier nodo esta unido a todos los otros un grafo completo son r nodos es llamado un r- grafo y de Nota como kr teorema: un r grafo no dirigido contiene exactamente representación d un grafo existen diversas formas de representar un grafo dirigido o no dirigido pero las más utilizadas son matriz de adyacencias y listas de adyacencias

27 10. Matriz de Adyacencias de un Grafo *sean G=(n,a)un grupo de nodos la matriz de adyancencias m para G es un matriz de valores boléanos donde M(i,j) es verdad si y solo si existen un arco desde el nodo i al nodo j: M(i,j)= 1 si existe el arco (i,j) 0, en caso contrario

28 Las filas de las columnas de l matriz representan los nodos del grafo Para un grafo no dirigido la matriz de adyacencias es simétrica La matriz de adyacencias es la misma matriz de la relaciones A de N pues indican cuales de los nodos están relacionados (unidos por un área)

29 Ejemplo: abcD A0110 B0011 C1001 D1000 b v d a La siguiente es la matriz de adyacencias del grafo orientado que se muestra M(i,j)=

30 Ejemplo:

31 Definición 2 Matriz de adyacencias representación de un grafo que consiste básicamente en un arreglo didimensional de tamaño nxn donde n es la máxima cantidad de nodos en el grado Cada casilla de la matriz será llenada con verdadero o falso según exista o no un arco que conecte los dos ndos involucrados

32 Definición 2 abcde AffvvV BffvVF CVvfFF DVVffV EVffvf Para el caso de las grafos no dirigidos la matriz es simétrica no así para los dígrafos

33 Definición 2 Para el caso de los grafo ponderadores puede llenarse con el peso asociado a cada de los arcos Su simplicidad es una ventaja Desventaja: limitada a un numero máximo de nodos en el grafo lo que implica que en cierto momento sea imposible almacenar mas información o que por el contrario si se supone un numero máximo muy grande se desperdicie una gran cantidad de memoria Para el caso de un grafo no dirigido el desperdicio seria mayor ya que al ser simétrica la matriz la información esta duplicada Ejemplo: un mensajero debe visitar los seis puntos que se muestran participando del punto que se muestran partiendo del punto a y terminando en el punto f el conoce la distancia que separa a cada par de puntos y desea establecer el recorrido que debe seguir para recorrer la mínima distancia y ahorrar tiempo

34 11. Lista de Adyacencias Sea G=(n,A) un grafo la lista de adyacencias para un nodo i es una lista en cualquier orden de todos los nodos adyacentes a i 1 4 3 2 1 2 3 4 6 5

35 12. Subgrafos Definición: un subgrafo de un grafo G=(v,n) es un grafo H=(v1,n1) tal que V1EVyN1EN Definición la unión de dos grafos simples G1=(V1,n1) y G2=(v2,n2) es el grafo (v1,uv2,n1un2 por lo tanto G1uG2

36 RESUMEN El estudio de estructuras de datos y de algoritmos es tan antiguo como el nacimiento de la programación y se ha convertido en estudio obligatorio en todos los currículos desde finales de los años sesenta y sobre todo en la década de los setenta cuando apareció el Lenguaje Pascal de la mano del profesor suizo Niklaus Wirtz, y posteriormente en la década de los ochenta con la aparición de su obra —ya clásica— Algorithms and Data Structures en 1986. Estructuras de Datos en C++ trata sobre el estudio de las estructuras de datos dentro del marco de trabajo de los tipos abstractos de datos (TAD) y objetos, bajo la óptica del análisis, diseño de algoritmos y programación, realizando las implementaciones de los algoritmos en C++.

37 1.Joyanes Aguilar, Luis. Estructura de Datos en Java. Primera edición. Ed. McGraw Hill. 2007. 2.2. Lewis, John. Estructura de Datos con JAVA: Diseño de estructuras y algoritmos. Primera edición. Ed. Pearson. 2007. 3.3. Guardati Buemo, Silvia. Estructura de Datos orientada a objetos: Algoritmos con C++. Primera edición. Ed. Pearson. 2007. 4.4. Allen, Marc. Estructura de Datos con JAVA: Compatible con JAVA 2. Ed. Prentice Hall. 5. Cairo, Osvaldo. Estructura de Datos. Tercera edición. Ed. McGraw Hill; 2006. REFERENCIAS

38 Bibliografía básica JOYANES, L. (2008). Fundamentos de la programación. Algoritmos y Estructura de Datos, 4ª Edición. Madrid: McGraw-Hill. JOYANES, L.; RODRIGUEZ, L; FERNANDEZ, M. (2003). Fundamentos de programación Libro de problemas. 2ª Edición. Madrid: McGraw-Hill. Bibliografía complementaria. AHO, Alfred V.; HOPCROFT, John E.; ULLMAN, Jeffrey D. (1998). Estructuras de datos y algoritmos. México: Addison Wesley. BRASSARD, G.; BRATLEY, P. (1997). Fundamentos de Algoritmia. Madrid: Prentice-Hall. COLLADO MACHUCA, M.; MORALES FERNÁNDEZ, R.; MORENO NAVARRO, J. J. (1987). Estructuras de datos. Realización en Pascal. Madrid: Ediciones Díaz de Santos. GARCÍA MOLINA, J. J.; MONTOYA DATO, F. J.; FERNÁNDEZ ALEMÁN, J. L.; MAJADO ROSALES, M. J. (2005). Una introducción a la programación. Un enfoque algorítmico. Madrid: Thomson-Paraninfo. JOYANES, L. (1990). Problemas de Metodología de la Programación. Madrid: McGraw-Hill. JOYANES, L.; ZAHOHERO, I. (2005). Programación en C : metodología, algoritmos y estructura de datos, 2ª Edición. Madrid: McGraw-Hill REFERENCIAS