GRAFOS

11

Tema 10- Grafos Duracin: 2 semanas aprox. ndice general:1. Relaciones entre los Datos de una Coleccin 2. Conceptos bsicos sobre Grafos3. Representacin de un Grafo: Matriz y Listas de

Adyacencia4. Implementacin de un Grafo en Java: las clases

Arista, Vertice y Grafo5. Recorrido de un Grafo: ampliacin de la clase Grafo6. Caminos Mnimos en un Grafo sin y con Pesos (Dijkstra):

la clase Java CaminosDelGrafo

Objetivos: 9 Estudio de la Representacin de una Relacin Binaria entre los

Datos de una Coleccin mediante la estructura Grafo y algunas de sus aplicaciones ms significativas. Ello permitir recapitular y ampliar conceptos y estructuras que se han estudiado a lo largo del curso, como: la ventaja de re-utilizar el Software que presenta la POO, al

estudiar las posibles Representaciones de un Grafo (Modelos Diccionario y Lista Con Punto de Inters ) y la implementacin de las operaciones de Recorrido y clculo de caminos mnimos sobre l (Modelos Cola y Cola de Prioridad)

las caractersticas de las Representaciones Lineal, Jerrquica y No Lineal de los Datos de una Coleccin para, respectivamente, su Acceso Secuencial, su Recorrido en Profundidad y Anchura y la Bsqueda Dinmica

9 Implementacin en Java de un Grafo, que supondr el diseo de las clases Arista, Vertice, Grafo y CaminosDelGrafo (ubicadas en el paquete grafos de estructurasDeDatos)

23

Bibliografa bsica:

9 Weiss, M.A. Estructuras de datos en Java. Adisson-Wesley, 2000.

Captulo 14, para conceptos sobre Grafos y Grafos Dirigidos

Captulo 22, apartado 22.2.3 para el algoritmo de Dijkstra con Montculos de Emparejamiento

9 Aho A.V., Hopcroft J.E., Ullman J.E. Estructuras de datos y Algoritmos. Addison-Wesley, 1988. Captulo 6 para conceptos sobre Grafos y Grafos Dirigidos

4

Sea un Coleccin cuyos Datos son: ciudades aeropuertos computadores de una red puntos del plano de una ciudad

Queremos modelar rutas entre ciudades rutas areas envo de correo electrnico recorridos tursticos

carreteras vuelos enlaces calles

Relaciones entre los Datos de la Coleccin

1) Representacin Lineal2) Representacin Jerrquica

35

10

35

Una Relacin R sobre un Conjunto S se define como un Conjunto de Pares (a, b): a, b S si (a, b) R se escribe a R b y denota que a est Relacionadocon b indica si cada Par de Datos del Conjunto estn o no Relacionados

Relacin Binaria entre los Datos de la Coleccin

3) Grafo cuyos Vrticesse Relacionan va Aristas

35

10

Relaciones entre los Datos de la Coleccin

6

9Grafos Dirigidos y no Dirigidos9Grafos Etiquetados9Relaciones de Incidencia y Adyacencia9Caminos

Conceptos bsicos sobre Grafos

47

Conceptos bsicos sobre Grafos: Grafos Dirigidos (Digrafos)

Un Grafo Dirigido (gd) es un Par G = (V,E)

9 V es un conjunto finito de Vrtices (o Nodos o Puntos) 9 E es un conjunto de Aristas (o Arcos) dirigidas

Arista: Par ordenado de Vrtices (u,v): u v

1 2 3

5 64

8

Conceptos bsicos sobre Grafos: Grafos no Dirigidos (Grafos)

Un Grafo no Dirigido (gnd) es un Par G = (V,E)

9 V es un conjunto finito de Vrtices 9 E es un conjunto de Aristas no Dirigidas

Arista: Par no ordenado de Vrtices (u,v) = (v,u), uv : u v

1 2 3

5 64

59

Conceptos bsicos sobre Grafos: Grafos Etiquetados

9 Un Grafo Etiquetado es un grafo G = (V,E) sobre el que se define una funcin f: E A, dnde A es un conjunto cuyas componentes se llaman Etiquetas

NOTA: la funcin de etiquetado se puede definir tambin sobre V, el conjunto de Vrtices

9 Un Grafo Ponderado es un Grafo Etiquetado (sus Aristas) con nmeros Reales (A )

Ejemplos: disctase la necesidad de etiquetar/ponderar los Grafos asociados a las aplicaciones reseadas en el primer punto del tema

10

Conceptos bsicos sobre Grafos: Relaciones de Incidencia

Sea G = (V,E) un Grafo Dirigido. Si (u,v) E, decimos que Incidedesde u (sale de ..) e Incide en v (llega a ..)

1 2 3

5 64

Sea G = (V,E) un Grafo no Dirigido. Si (u,v) E, decimos que Incide sobre u y v

1 2 3

5 64

611

1 2 3

5 64

Sea G = (V,E) un Grafo. Si (u,v) E, decimos que el Vrtice v es Adyacente al Vrtice u

En un Grafo no Dirigido la relacin es simtrica

1 2 3

5 64

Conceptos bsicos sobre Grafos: Relaciones de Adyacencia

12

Conceptos bsicos sobre Grafos: Grado de un Vrtice

1 2 3

5 64

El Grado de un Vrtice en un Grafo no Dirigido es el nmero de Aristas que Inciden sobre l

El Grado de un Vrtice en un Grafo Dirigido es la suma de: el nmero de Aristas que salen de l (Grado de Salida) el nmero de Aristas que entran en l (Grado de Entrada)

1 2 3

5 64

( Vrtices Adyacentes )

713

1 2 3

5 64

El Grado de un Grafo es el de su Vrtice de mximo Grado

Conceptos bsicos sobre Grafos: Grado de un Grafo

14

Conceptos bsicos sobre Grafos: Caminos

9 Un Camino de longitud k desde u a u en un grafo G=(V,E) es una secuencia de Vrtices v0,v1,..,vk tal que: vo = u y vk = u i : 1..k : (vi-1,vi) E la longitud k del Camino es el nmero de Aristas la longitud del Camino con Pesos es la suma de los Pesos de

las Aristas que forman el Camino9 Si hay un Camino P desde u hasta u, decimos que u es

alcanzable desde u va P1 2 3

5 64

815

Conceptos bsicos sobre Grafos: Caminos Simples y Ciclos

9 Un Camino es Simple si todos sus Vrtices son distintos9 En un Grafo Dirigido un Camino v0,v1,..,vk forma un Ciclo si:

vo = vk el Camino contiene al menos una Arista

9 El Ciclo es Simple si todos sus Vrtices son distintos9 Un Bucle es un Camino de longitud 19 Un Grafo Dirigido es Acclico si no contiene Ciclos (GDA)

1 2 3

5 64

16

9 En un Grafo no Dirigido un Camino v0,v1,..,vk forma un Ciclo si: vo = vk si todos los vi son distintos

9 Un Grafo no Dirigido es Acclico si no contiene Ciclos

1 2 3

5 64

Conceptos bsicos sobre Grafos: Caminos Simples y Ciclos

9Ejemplo: sea G = (V,E) un Grafo Dirigido con PesosV={v0,v1, v2, v3, v4, v5, v6 },

E={ (v0,v1, 2), (v0,v3, 1), (v1,v3, 3), (v1,v4, 10),

(v3,v4, 2), (v3,v6, 4), (v3,v5, 8), (v3,v2, 2),

(v2,v0, 4), (v2,v5, 5), (v4,v6, 6), (v6,v5, 1) }

Se pide: 1.- |V| y |E|2.- Vrtices adyacentes a cada vi 3.- Grado de cada vi y del Grafo 4.- Caminos desde v0 al resto de Vrtices, su longitud con y sin Pesos 5.- Vrtices alcanzables desde v06.- Caminos mnimos desde v0 al resto de Vrtices7.- Tiene ciclos?

18

0 1 2 3 4 5

0

1

2

3

4

5

Representacin de un Grafo: Matriz de Adyacencia

0 1 2

4 53

falsefalsefalsefalsefalsefalse

falsetruefalsefalsefalse

falsefalsefalsefalsefalse


truefalse false false false false

truetruefalse false false

true

Un Grafo G=(V,E) se representa con una Matriz de|V|x|V| boolean: si (u,v) E, G[u,v] = true; sino G[u,v] = false

true

true

true

true

9 Memoria: O(|V|2)9 Tiempo de acceso: O(1)

10

19

0 1 2 3 4 5

0

1

2

3

4

5

truefalse false false false

true truefalse false false false

true

0 1 2

4 53

true

true

true

true

falseflasefalsefalsefalse

falsefalsefalsefalsefalsefalse

falsefalsefalsefalse


Un Grafo G=(V,E) se representa con una Matriz de|V|x|V| boolean: si (u,v) E, G[u,v] = true, sino G[u,v] = false

Representacin de un Grafo: Matriz de Adyacencia

20

0 1 2

4 53

Un Grafo G=(V,E) se representa con un array de|V| Listas de Vrtices: G[v], v V, es una Lista de los Vrtices Adyacentes a v9 Memoria: O(|V|+|E|)9 Tiempo de acceso: O(Grado de G)

X

1 |X

1 | 3 |

4 |X

4 |X

3 |X2 |X

0 |

0

1

2

3

4

5

Representaciones de un Grafo: Listas de Adyacencia

11

21

Ejemplo propuesto: representar los siguientes Grafos

22

0 1 2

4 53

GrafoV0 representa un Grafo de Vrtices sin Etiquetar, i.e. de tipo int de Aristas sin Pesos, i.e. Pares de intmediante Listas de Adyacencia (array de|V| Listas de Vrtices)

Implementacin de un Grafo en Java: la clase GrafoV0

X

1 |X

1 | 3 |

4 |X

4 |X

3 |X2 |X

0 |

0

1

2

3

4

5

12

23

package grafos;

import modelos.*; import lineales.*;

public class GrafoV0 {/** Representa un Grafo Bsico mediante Listas de Adyacencia

* i.e. como un array de|V| Listas Con PI de Integer */protected ListaConPI elArray[];

public GrafoV0(int numVertices){...}

public void insertarArista(int origen, int destino){...}

public String toString(){...}

}

Implementacin de un Grafo en Java: la clase GrafoV0

package grafos; import modelos.*; import lineales.*; public class GrafoV0 {

protected ListaConPI elArray[];public GrafoV0(int numVertices){

}public void insertarArista(int origen, int destino){

}public String toString() {

}

elArray = new ListaConPI[numVertices];for ( int i=0; i numVertices; i++ ) elArray[i] = new LEIListaConPI();

La clase GrafoV0

elArray[origen].inicio();elArray[origen].insertar(new Integer(destino));

String res = ; for ( int i = 0; i < elArray.length; i++ )

if ( elArray[i].esVacia() ) res += Vrtice +i+ sin Adyacentes;else res += Vrtice +i+ con Adyacentes+elArray[i].toString();

return res;

13

Ejemplo propuesto: escrbase un programa cuya salida sea la que se muestra a continuacin y dibjese el Grafo ledo.

Indique el nmero de Vrtices del Grafo: 6Grafo inicializado:Vrtice 0 sin AdyacentesVrtice 1 sin AdyacentesVrtice 2 sin AdyacentesVrtice 3 sin AdyacentesVrtice 4 sin AdyacentesVrtice 5 sin AdyacentesIntroduzca Arista (Par de Vrtices separados por blancos):0 10 41 01 42 54 04 15 2Grafo construido:Vrtice 0 con Adyacentes 4 1Vrtice 1 con Adyacentes 4 0Vrtice 2 con Adyacentes 5Vrtice 3 sin AdyacentesVrtice 4 con Adyacentes 1 0Vrtice 5 con Adyacentes 2

0 1 2

4 53

26

0 1 2

4 53

GrafoV1 representa un Grafo de Vrtices sin Etiquetar, i.e. de tipo int de Aristas con Pesos, Tripletes de int (origen, destino, coste)mediante Listas de Adyacencia (array de|V| Listas de Vrtices)

777

3

3

3

8

2 (1,3) |X

(1,2) | (3,8) |

(4,7) |X

(4,7) |X

(3,3) |X(2,7) |X

(0,7) |

X

0

1

2

3

4

5

Implementacin de un Grafo Ponderado en Java: la clase GrafoV1

14

27

La clase Java Arista

package grafos;class Arista {

int destino;int coste;Arista(int d, int c){ destino = d; coste = c;}public String toString(){ return destino + (+ coste+ ); }

}

28

package grafos;

import modelos.*; import lineales.*;

public class GrafoV1 {

protected ListaConPI elArray[];

public GrafoV1(int numVertices){...}public void insertarArista(int origen, int destino, int coste){

}


}

La clase GrafoV1

elArray[origen].inicio();elArray[origen].insertar(new Arista(destino, coste));

15

29

Grafo representa un Grafo de Vrtices con Etiquetas, i.e. Pares (etiqueta, n vrtice) de Aristas con Pesos, i.e. Tripletes de intmediante Listas de Adyacencia ( array de |V| Vrtices)

777

3

3

3

8

2

v2

v5

v0 v1

v3 v4

(v0, )

(v1, )

(v2,x)

(v3, )

(v4, )

(v5, )

(1,3) |X

(1,2) | (3,8) |

(4,7) |X

(4,7) |X

(3,3) |X(2,7) |X

(0,7) |

0

1

2

3

4

5

Implementacin de un Grafo Ponderado con Vrtices Etiquetados en Java:

la clase Grafo

La clase Java Verticepackage grafos; import modelos.*; import lineales.*;class Vertice {

String nombre; int codigo;ListaConPI listaAdy;Vertice(String n){ this(n, -1);}Vertice(String n, int c){

nombre = n; codigo = c;listaAdy = new LEIListaConPI();

}}

Cmo obtener codigo de un Vrtice a partir de su nombre ?Al insertar un Vrtice en un Grafo se actualiza un Diccionario deVrtices con una nueva Entrada tal que su clave == nombre ysu codigo == ordenInsercionVertice

16

31

Ejemplo: insercin de una Arista, Par de Vrtices, en Grafo

D C 10

Diccionario de Vrtices

..........

D D, ? buscar(D)Vrtice 0:

Grafo (vaco)|V| = 0

32


D C 10


..........

D D,? buscar(D)ElementoNoEncontrado

0Vrtice 0:

Grafo (vaco)|V| = 0

17

33


D C 10


..........

D, 0

D, insertar((D, 0))0Vrtice 1:

0D

Grafo |V| = 01

34


D C 10


..........

C C, ? buscar(C)

ElementoNoEncontrado

1Vrtice 2:

D, 0

0D

Grafo |V| = 1

18

35


D C 10


..........

C, insertar((C, 1))1Vrtice 2:

D, 0

0D

Grafo |V| = 1

C, 1

2

1C

10

10

36


D B 23


..........

D, 0

0D

Grafo |V| = 2

C, 1

1C

10

D D, ? buscar(D)ElementoDuplicado

0Vrtice 3:

19

37

package grafos;

import modelos.*; import excepciones.*;

import lineales.*; import noLineales.*;

public class Grafo {

protected Vertice elArray[];

public Grafo(int numVertices){...}

public void insertarArista(String nO, String nD, int coste){...}


protected Diccionario dicVertices;protected int ordenInsercionVertice;

public int insertarVertice(String nO){...}

}

La clase Grafo

public Grafo(int numVertices){

}public String toString() {

}public void insertarArista(String nO, String nD, int coste){

}

La clase Grafo

20

39

public int insertarVertice(String nombreVertice) {int res = -1;Vertice v = new Vertice(nombreVertice); try { res = ((Vertice)dicVertices.buscar(v)).codigo; }catch(ElementoNoEncontrado e){

res = v.codigo = ordenInsercionVertice;try { dicVertices.insertar(v); }catch(ElementoDuplicado ed){;}elArray[res] = v;ordenInsercionVertice++;

}return res;

}

La clase Grafo

40

Ejemplo propuesto: definir el mtodo toString en Grafo de forma que se muestren siempre los Vrtices mediante sus etiquetas, y no con la representacin numrica interna

21

41

9 Mtodo constructor para crear un Grafo a partir de la informacin de Aristas/Vrtices leda desde un fichero

9 Mtodo para consultar el nmero total de Aristas de un Grafo9 Mtodo para consultar el Grado de un Vrtice dado de un Grafo

(Grado de Salida si el Grafo es Dirigido)9 Mtodo para consultar el Grado de un Grafo (Grado de Salida si

el Grafo es Dirigido)9 Mtodo para consultar si un Grafo est Vaco9 Mtodo para consultar si una Arista dada pertenece a un Grafo

Ejemplo propuesto: definir los siguientes mtodos de la clase Grafo

Ejemplos resueltos: los que aparecen en los exmenes disponibles en la MicroWeb de la asignatura

Date post:	19-Oct-2015
Category:	Documents
Upload:	stephany-azucena-damian-ortega
View:	9 times
Download:	0 times

GRAFOS

Documents