S8-EDD-4.2 Aplicaciones de árboles en informática

S8-EDD-4.2 Aplicaciones de árboles en informática

1. Estructuras de Datos Tema: 4 Estructura de datos dinámicas tipo Árboles Docente: Mg. Luis Fernando Aguas B

2. Los éxitos más importantes se consiguen cuando existe la posibilidad de fracasar – Mark Zuckerberg

3. Objetivo Adquirir los conceptos básicos relacionados con las EDD Reconocer las características de las EDD 4.2 Aplicaciones de árboles en informática Contenido

4. 4.2 Aplicaciones de árboles en informática

5. Grafos en cualquier parte

6. Grafos en computación Interés típico en vértices y lados como objetos (ej. Redes de comunicación) objetos con propiedades

7. Grafos en computación Gran interés en grafos dirigidos para aplicaciones Redes para comunicaciones Sistemas de transporte Computación distribuida Java: Jerarquías, instancias, mensajes

8. Grafo Dirigido Definición Un Grafo Dirigido , o diGrafo  , es uno o varios pares G = (V, E) con las siguientes propiedades: El primer componente, V, es un finito, conjunto no-vacio. Los elementos de V son llamados vértices de G. El segundo componente, E, es un conjunto finito uno o varios pares de vértices. Esto es, E  V x V . Los elementos son llamados los arcos de G. Ejemplo G = (V, E) V = {a, b, c, d} E = { (a,b), (a,c), (b,c), (c,a), (c,d), (d,d) } Recuerde E no puede tener mas de una instancia de un arco. (a,b) es diferente de (b,a). Ej. Considere un paso a desnivel (a,b). Aunque la distancia es la misma, el tiempo para atravesar del a2b y b2a puede ser diferente.

9. Grafo Dirigido... Head, Tail, Adyacente Terminología Considere un Grafo Dirigido G = (V, E). cada elemento de V es llamado un vértice   o un nodo   de G. Así, V es el conjunto de vértices (o nodos) de G. cada elemento de E es llamado un arco   de G. Así, E es el conjunto de arcos de G. Un arco (v,w)  E puede ser representado como v  w . Una flecha apunta desde v a w es conocido como un arco dirigido . El vértice w es llamado la cabeza ( head) del arco porque es el inicio de la flecha. Convencionalmente, v es llamado la cola ( tail) del arco. Finalmente, vértice w es llamado Adyacente   al vértice v.

10. Grafo Dirigido... Out-degree, In-degree Terminología Considere un Grafo Dirigido G = (V, E). Un arco e=(v,w) se dice que emana  desde el vértice v. Usamos la notación A(v) el conjunto de arcos que emanan desde el vértice v. Así, A(v) = {(a,b)  E : a=v } El grado de salida ( out-degree)  de un nodo es el número de arcos que salen desde el nodo. Sin embargo, el grado de salida de v es |A(v)| Un arco e=(v,w) se dice incidente  en vértice w. usamos la notación I(w) para denotar el conjunto de arcos incidentes en vértice w. Tal que, I(w) = {(a,b)  E : b=w } El grado de entrada ( in-degree )  de un nodo es el número de arcos incidentes en aquel nodo. Sin embargo, el in-degree de w es |I(v)|

11. Grafo Dirigido... camino Definición Un camino  en un Grafo Dirigido G = (V, E) es una secuencia no vacía de vértices P = {v 1 , v 2 , ..., v k } donde v i  V para 1  i  k tal que (v i , v i+1 )  E para 1  i  k. La longitud ( longitud ) del camino P es k -1. Ejemplo P 1 = (a) P 2 = (b, c) P 3 = (a, b, c) P 4 = (a, c, a, c, a, c, a, c, a, c, a, c, a) Pregunta Cual es la máxima longitud del camino?

12. Grafo Dirigido... Sucesor , Predecesor Terminología Considere el camino P = {v 1 , v 2 , ..., v k } en Grafo Dirigido G = (V, E). vértice v i+1 es el Sucesor  de vértice v i para 1  i < k. cada elemento v i del camino P (excepto el ultimo) tiene un Sucesor . vértice v i-1 es el Predecesor del vértice v i para 1 < i  k. cada elemento v i del camino P (excepto el primero) tiene un Predecesor. Ejemplo {a, b, c, d}

13. Grafo Dirigido... Camino simple, ciclo, Lazo Terminología Considere el camino P = {v 1 , v 2 , ..., v k } en Grafo Dirigido G = (V, E). A camino P es llamado un Camino simple si y solo si v i  v j para todo i y j tal que 1  i < j  k . Sin embargo, esto es permitido para v 1 = v k . Un ciclo   es un camino P de longitud no-cero en donde v 1 = v k . La longitud de un ciclo es justo la longitud del camino P. Un Lazo   es un ciclo de longitud uno. Así, este es un camino de la forma {v, v}. Un simple ciclo    es un camino que es ambos un ciclo y simple. Ejemplo {a, b, c, d} {c, a, c, d} {a, b, c, a} {a, c, a, c, a}

14. Grafo Dirigido... Grafo Dirigido Acíclico Definición Un Grafo Dirigido Acíclico (DAG)  es un Grafo Dirigido que no contiene ciclos. Recuerde árboles  DAG. DAG  árbol

15. Grafo No Dirigido Definición Un Grafo No Dirigido es un par ordenado G = (V, E) con las siguientes propiedades: El primer componente, V, es un conjunto finito, no vacío. Los elementos de V son llamados los vértices de G. El segundo componente, E, es un conjunto finito. cada elemento de E es un conjunto que esta compuesto exactamente de dos (distintos) vértices. los elementos de E son llamados los arcos de G. Ejemplo G = ( V, E) V = {a, b, c, d} E = { {a,b}, {a,c}, {b,c}, {c,d} } Recuerde {a,b} = {b,c}  No Dirigido *ej. Comunicación full duplex.

16. Grafo No Dirigido... Incide Terminología Considere un Grafo No Dirigido G = (V, E). Un arco e={v,w}  E se dice que emana desde y incide en ambos vértices v y w. El conjunto de arcos que emanan desde un vértice v es el conjunto A(v) = {(v ,v 1 )  E : v = v  v 1 = v } El conjunto de arcos incidentes en un vértice w es I(w) = A(w)

17. Grafo etiquetados Definición Un Grafo que ha sido anotado en alguna forma es llamado un Grafo etiquetado . Recuerde ambos arcos y vértices puede ser etiquetados

18. Representación Considere un Grafo Dirigido G = (V, E). Si E  V  V, Grafo G contiene al menos |V| 2 arcos. Existe posibles conjuntos de arcos para un conjunto dado de vértices.

19. Representación ... Matriz Adyacente para DAG Considere a Grafo Dirigido G = (V, E) con V = {v 1 , v 2 , ..., v n }. La representación simple del Grafo usa una matriz n x n de ceros o unos dados por La matriz A es llamada matriz adyacente .

20. Representación ... Matriz adyacente para DAG ... Ejemplo Recuerde El número de unos en la matriz adyacente es igual al número de arcos en el Grafo Cada uno en la i th fila corresponde a un arco que emana desde vértice v i . Cada uno en la i th columna corresponde a un arco que incide en vértice v i .

21. Representación ... Matriz adyacente para No Dirigido Representa un Grafo No Dirigido G = (V, E) con V = {v 1 , v 2 , ..., v n }, usando una matriz n x n A de ceros y unos dado por

22. Representación ... Matriz adyacente para No Dirigido ... Ejemplo Recuerde Sea {v i , v j } = { v j , v i }, matriz A es simétrica cerca de la diagonal. Esto es, a ij = a ji Todas las entradas en la diagonal son cero. Esto es, a ii = 0 para 1  i  n

23. Representación ... Matriz adyacente para No Dirigido ... Ejemplo Recuerde Sea {v i , v j } = { v j , v i }, matriz A es simétrica cerca de la diagonal. Esto es, a ij = a ji Todas las entradas en la diagonal son cero. Esto es, a ii = 0 para 1  i  n

24. Representación > matriz adyacente... Complejidad Sea la matriz adyacente tiene |V| 2 entradas, la cantidad de espacio necesaria para representar los arcos de un Grafo es O( |V| 2 ) depende del número actual de arcos en el Grafo. Si |E| << |V| 2 entonces muchas de entradas son 0 Excelente Representación !

25. Representación > Matriz adyacente ... Grafos dispersos y densos Definición Un Grafo disperso  es un Grafo G = (V, E) en donde |E| = O( |V| ) Definición Un Grafo denso  es un Grafo G = (V, E) en donde |E| =  ( |V| 2 )

26. Representación > Matriz adyacente... Listas Adyacentes

27. Representación Comparación de Representaciones operación Matriz adyacente Lista adyacente Buscar arco (v,w) O(1) O( |A(v)| ) Enumerar todos los arcos O( |V| 2 ) O( |V| + |E| ) enumerar arcos que emanan de v O( |V| ) O( |A(v)| ) enumerar arcos inciden en w O( |V| ) O( |V| + |E| )

28. Implementación

29. Grafo en JAVA - vértice class Vertex { public String name; // Vertex name public LinkedList<Edge> adj; // edges from vertex public double dist; // Cost public Vertex prev; // Previous vertex on shortest path public int scratch; // Extra variable used in algorithm public Vertex( String nm ) { name = nm; adj = new LinkedList<Edge>( ); reset( ); } public void reset( ) // clears values used in algorithms { dist = Graph.INFINITY; prev = null; scratch = 0; } }

30. Grafo en JAVA - lado class Edge { public Vertex dest; // Second vertex in Edge public double cost; // Edge cost public double temp; // used in algorithms public Edge( Vertex d, double c ) { dest = d; cost = c; } }

31. Grafo en JAVA public class Graph { public static final double INFINITY = Double.MAX_VALUE; private HashMap<String,Vertex> vertexMap = new HashMap(); // maps String to Vertex public void addEdge( String sourceName, String destName, double cost ) { Vertex v = getVertex( sourceName ); Vertex w = getVertex( destName ); v.adj.add( new Edge( w, cost ) ); }

32. Grafo Transversal Primer nivel Transversal Similar a árbol Primer nivel Transversal Porque no existe raíz, debemos especificar un nodo inicial Porque un Grafo puede ser cíclico, debemos prevenir la recursion infinita

33. Grafo Transversal Primer nivel Transversal ... El Primer nivel Transversal visita los nodos en el orden c, a, b, d Recuerde Un Primer nivel Transversal solo sigue arcos que dirige a vértices no visitados. Si omitimos los arcos que no son seguidos, los arcos remanentes forman un árbol. El Primer nivel Transversal de este árbol es equivalente a el Primer nivel Transversal del Grafo .

34. Grafo Primer nivel Transversal Implementación public abstract class AbstractGrafo extends AbstractContainer implements Grafo { ... public void depthprimerTransversal(PrePostVisito prepostvisito , int i) { boolean aflag[] = new boolean [númeroOfVertices]; fo ( int j = 0; j < númeroOfVertices; j++) aflag[j] = false ; depthprimerTransversal(prepostvisito , vértice[i], aflag); } private void depthprimerTransversal( PrePostVisito prepostvisito , vértice vértice1, boolean aflag[]) { if (prepostvisito .isDone()) return ; prepostvisito .preVisit(vértice1); aflag[vértice1.getnúmero()] = true ; fo (Enumeration enumeration = vértice1.getSucesor s(); enumeration.hasMo eelementos(); ) { vértice vértice2 = (vértice) enumeration.nextelemento(); if (!aflag[vértice2.getnúmero()]) depthprimerTransversal(prepostvisito , vértice2, aflag); } prepostvisito .postVisit(vértice1); } }

35. Grafo Transversal Primer hondo Transversal Similar a árbol Primer hondo Transversal Utiliza una cola de vértices Debido a que no existe raíz, debemos especificar un nodo de partida Porque un Grafo puede ser cíclico, debemos asegurarnos que un vértice este encolado solamente una vez

36. Grafo Transversal Primer hondo Transversal ... El Primer hondo Transversal visita los nodos en el orden a, b, c, d

37. Grafo Primer hondo Transversal ... Implementación public abstract class AbstractGrafo extends AbstractContainer implements Grafo { ... public void breadthprimerTransversal(Visito visito , int i) { boolean aflag[] = new boolean [númeroOfVertices]; fo ( int j = 0; j < númeroOfVertices; j++) aflag[j] = false ; QueueAsLinkedList queueaslinkedlist = new QueueAsLinkedList(); aflag[i] = true ; queueaslinkedlist.enqueue(vértice[i]); while (!queueaslinkedlist.isvacio() && !visito .isDone()) { vértice vértice1 = (vértice) queueaslinkedlist.dequeue(); visito .visit(vértice1); fo (Enumeration enumeration = vértice1.getSucesor s(); enumeration.hasMo eelementos(); ) { vértice vértice2 = (vértice) enumeration.nextelemento(); if (!aflag[vértice2.getnúmero()]) { aflag[vértice2.getnúmero()] = true ; queueaslinkedlist.enqueue(vértice2); } } } } ... }

38. Grafo Transversal Orden Topológico Definición Considere a Dirigido aciclico Grafo G = (V, E). Un Orden Topológico de los vértices de G es una secuencia S = { v 1 , v 2 , ..., v |V| } en donde cada elemento de V aparece exactamente una vez. Para cada par de distintos vértices v i y v j en la secuencia S, si v i  v j es un arco en G, i.e., (v i , v j )  E, entonces i < j.

39. Grafo Transversal Orden Topológico Transversal Un Transversal que visita los vértices de un DAG en el orden dado por el Orden Topológico Calcula el grado interno de los vértices Repetidamente selecciona el vértice con cero grado, visita y entonces “remuévelo del Grafo” S 1 = { a, b, c, d, e, f, g, h, i } S 2 = { a, c, b, f, e, d, h, g, i } S 3 = { a, b, d, e, g, c, f, h, i } ... Existe muchos

40. Esta conectado Existe algún ciclo Grafo Transversal Aplicaciones 1 0 2 3 9 4 8 7 5 6 7

41. Grafo Transversal > Aplicaciones conexión Definición Un Grafo No Dirigido G = (V, E) esta conectado  si existe un camino en G entre cada par de vértices in V. Los sub-Grafos conectados de un Grafo son llamados componentes conectados .

42. Grafo Transversal > Aplicaciones conexión Definición Un Grafo Dirigido G = (V, E) esta fuertemente conectado  si existe un camino en G entre cada par de vértices en V. Definición Un Grafo Dirigido G = (V, E) esta débilmente conectado  si el Grafo subrayado No Dirigido Ğ esta conectado.

43. Grafo Transversal > Aplicaciones conexión Algoritmo Para todos los vértices Partir de cada vértice Atravesar el Grafo Marque cada vértice visitado Si existe un vértice no visitado, no conectado Aplique topológico o der Transversal

44. Camino mas corto Distancia Distancia entre dos vértices 2-9 3-9 7-4 1 0 2 3 9 4 8 7 5 6 7

45. Camino mas corto peso de camino Definición Considere el peso de un arco Grafo G = (V, E) . Sea C( v i ,v j ) el peso del arco que conecta v i a v j . Un camino en G es una secuencia no vacía de vértices P = {v 1 , v 2 , ..., v k }. El peso del camino P esta dado por

46. Camino mas corto Fuente simple Definición Fuente simple - Camino mas corto problema Dado un peso-arco Grafo G = (V, E) y un vértice v s  V , buscar el menor peso del camino desde v s a otro vértice en V. Recuerde si todos los pesos son positivos, esta bien definido.

47. Si el Grafo es aciclico, el problema es fácil Haga un Orden Topológico Transversal Si todos los pesos-arcos no son negativos el problema de camino corto esta bien definido Un Algoritmo trabaja bien (Ej. Algoritmo Dijkstra) Camino mas corto Caso especial: pesos no negativos

48. Si el Grafo tiene pesos negativos (pero no ciclos de costo negativo) una solución existe pero el Algoritmo greddy no trabaja. Si el Grafo tiene un ciclo de costo negativo, No existe solución. Camino mas corto Casos especiales: pesos negativos

49. Camino mas corto Algoritmo Dijkstra Desde el conjunto de vértices para k v = false, seleccione el vértice v tome la tentativa distancia d v . Ponga k v = true Para cada vértice w adyacente a v para cada k v  true, pruebe el peso tentativo de d v si es mayor que d v + c(v,w). Si es así, ponga d v  d v + c(v,w) y ponga p v  v. En cada paso exactamente un vértice tiene este k v ponga a true. El Algoritmo termina después |V| pasos son completados cuando todos los caminos mas cortos son conocidos

50. Camino mas corto Algoritmo Dijkstra k v indica que el Camino mas corto de vértice v es conocido. Inicialmente falso d v la longitud del camino corto conocido desde v s a v. Inicialmente . p v el Predecesor de vértice v en el Camino mas corto desde v s a v. Inicialmente desconocido.

51. Camino mas corto : Dijkstra

52. Análisis del camino critico ANALISIS Actividad de nodos Caminos críticos Eventos en nodos Tiempos de eventos tempranos o tardíos Actividad critica EJERCICIO BASADO EN GRAFO SIGUIENTE: Determine un camino entre e y f; f y a Determine si tiene ciclo d, f Determine si existe lazo en c, d

53. EJERCICIO - GRAFO a b c e f g d 15 5 6 4 7 6 5 12 3 7

54. Gracias Responsabilidad con pensamiento positivo