Tema 9: GRAFOSPrimera Parte

Estructuras de Datos y AlgoritmosCurso 2002/03

Grafos. EDA. Curso 2002/032

OBJETIVOS

Definiciones formales de grafo y conceptos relacionadosEstructuras de datos para representar grafosAlgoritmos para resolver diferentes variantes del problema deencontrar el camino mnimo sobre un grafoAlgoritmos para resolver el problema de encontrar el rbol deextensin de coste mnimo sobre un grafo

Grafos. EDA. Curso 2002/033

NDICE

1. Introduccin2. Conceptos Bsicos3. Implementacin de grafos4. Recorridos de grafos5. Bsqueda del camino con peso mnimo: algoritmo de Dijkstra6. Otros problemas de caminos en GAD

Ordenacin topolgicaBsqueda de caminos mnimos

7. Problema de obtencin de rboles de extensin sobre grafosno dirigidos

Algoritmos de Prim y Kruskal

Grafos. EDA. Curso 2002/034

BIBLIOGRAFA

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

Captulos 14 y 23

Otros:T.H. Cormen, C.E. Leiserson, R.L. Rivest. Introduction to Algorithms. MITPress, 1990.

Captulos 5 y 23.Aho A.V., Hopcroft J.E., Ullman J.E. Estructuras de datos y Algoritmos.Addison-Wesley, 1988.

Captulos 6 y 7.

Grafos. EDA. Curso 2002/035

1. INTRODUCCIN

Un grafo permite representar relaciones binariasrelaciones binarias entre loselementos de un conjunto.

18

30

23

2535

4921

39

25

Ejemplos:Rutas de transporteEnvo de correo electrnico

Grafos. EDA. Curso 2002/036

CONCEPTOS BSICOS

Grafos dirigidos y no dirigidosGrafos etiquetadosRelaciones de incidencia y adyacenciaCaminosSubgrafosConectividadrboles y Grafos

Grafos. EDA. Curso 2002/037

Grafos Dirigidos (DiGrafos)

Un grafo dirigidografo dirigido (g.d.) es un par G=(V,E)V es un conjunto finito de vrtices (nodos)E es un conjunto de arcos (o aristas). Un arco es un parordenado(u,v) con u,vV

1 2 3

5 64

V={1,2,3,4,5,6}

E={(1,2),(2,2),(2,4),(2,5),(4,1), (4,5),(5,4),(6,3)}

Grafos. EDA. Curso 2002/038

Un grafo no dirigidografo no dirigido (G.N.D) es un par G=(V,E)V es un conjunto finito de vrtices (nodos)E es un conjunto de arcos (aristas). Un arco es un par NO ordenado(u,v) con u,vV, uv

Grafos no dirigidos

V={1,2,3,4,5,6}

E={(1,2),(1,5),(2,5),(3,6)}

1 2 3

5 64

Grafos. EDA. Curso 2002/039

Grafos Etiquetados

Un grafo etiquetado es un grafo G=(V,E) sobre el que se defineuna funcin f:E->A, dnde A es un conjunto cuyas componentesse llaman etiquetas.Un grafo ponderado (o con pesos o costes) es un grafoetiquetado con nmeros reales (A)

Grafos. EDA. Curso 2002/0310

Relaciones de Incidencia y Adyacencia

Sea G=(V,E) un grafo dirigido. Si (u,v)E, decimos que incideincidedesdedesde u (sale de..) e incide enincide en v (llega a..).Ejemplo: vrtice 2

1 2 3

5 64

Grafos. EDA. Curso 2002/0311

Relaciones de Incidencia y Adyacencia (cont.)

Sea G=(V,E) un grafo no dirigido. Si (u,v)E, decimos que incideincidesobresobre u y v.Ejemplo: vrtice 2

1 2 3

5 64

Grafos. EDA. Curso 2002/0312

Relaciones de Incidencia y Adyacencia (cont.)

Sea G=(V,E) un grafo. Si (u,v)E, decimos que el vrtice v esadyacenteadyacente al u.

La relacin es simtrica en grafos no dirigidos

1 2 3

5 64

2 es adyacente a 11 es adyacente a 2

1 2 3

5 64

2 es adyacente a 11 NO es adyacente a 2

Grafos. EDA. Curso 2002/0313

Relaciones de Incidencia y Adyacencia (cont.)

Llamaremos grado de un vrticegrado de un vrtice en un g.n.d. al n de arcos queinciden sobre l.

1 2 3

5 64

El grado de 2 es 2

Grafos. EDA. Curso 2002/0314

Relaciones de Incidencia y Adyacencia (cont.)

El grado de un vrticegrado de un vrtice en un g.d. es el n de arcos que salen del (grado de salida) ms el n de arcos que entran (grado deentrada).

1 2 3

5 64

Grado de entrada del 2=2, Grado de salida del 2 =3Grado de 2=5

Grafos. EDA. Curso 2002/0315

Relaciones de Incidencia y Adyacencia (cont.)

El grado de un grafo es el del vrtice de mximo grado.

1 2 3

5 64

El grado de este grafo es 5

Grafos. EDA. Curso 2002/0316

Caminos

Un caminocamino de de longitud klongitud k desde desde uu a a uu en un grafo G=(V,E) esuna secuencia de vrtices v0,v1,..,vk tal que vo=u y vk=u yi:1..k:(vi-1,vi)E. La longitud del camino es el nmero de arcos.La longitud del camino con pesos es la suma d elos costes de lasaristas que forman el caminoSi hay un camino P desde u hasta u, decimos que u esalcanzablealcanzable desde u via P.

Grafos. EDA. Curso 2002/0317

Caminos (cont.)

Un caminocamino es simplesimple si todos sus vrtices son distintos.

1 2 3

5 64

es un camino simple de longitud 3

no es un camino simple

Grafos. EDA. Curso 2002/0318

Caminos (cont.)

En un g.d. un camino forma un ciclociclo si v0=vk y elcamino contiene al menos un arco.

El ciclo es simple si los vrtices son distintosUn bucle es un ciclo de longitud 1

1 2 3

5 64

es un ciclo

Grafos. EDA. Curso 2002/0319

Caminos (cont.)

En un g.n.d. un camino forma un ciclociclo si v0=vk ylos vi son distintos.Un grafo sin ciclos diremos que es acclico acclico (GDA)(GDA)

Grafos. EDA. Curso 2002/0320

Ejercicio

Sea G = (V,E) un Grafo dirigido con pesosV={v0,v1, v2, v3, v4, v6, 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 vi3.- Grado de cada vi y del Grafo4.- Caminos desde v0 al resto de Vrtices, su longitud y su longitud con pesos5.- Vrtices alcanzables desde v06.- Caminos mnimos desde v0 al resto de Vrtices7.- Tiene ciclos?

Grafos. EDA. Curso 2002/0321

Subgrafos

Un grafo G=(V,E) es un subgrafo de G=(V,E) si VV y EE.Dado un conjunto VV, el subgrafo de G inducido por V esG=(V,E):E={(u,v)E:u,vV}

1 2 3

6

Ejemplo: subgrafo inducido por {1,2,3,6}

1 2 3

5 64

Grafos. EDA. Curso 2002/0322

Conectividad de un grafo

Un g.n.d. es conexoconexo si cualquier par de vrtices estnconectados por un camino. Las componentes conexascomponentes conexas de ungrafo son las clases de equivalencia en V definidas por larelacin es alcanzable desde..

1 2 3

5 64

Grafos. EDA. Curso 2002/0323

Conectividad de un grafo (cont.)

Un g.d. es fuertemente conexofuertemente conexo si cualquier vrtice esalcanzable desde cualquier otro. Las componentescomponentesfuertemente conexasfuertemente conexas de un grafo son las clases deequivalencia en V definidas por la relacin son mutuamentealcanzables

1 2 3

5 64

Grafos. EDA. Curso 2002/0324

rboles

Un bosquebosque es un grafo acclico no dirigido.Un grafo acclico, no dirigido y conexo es un rbol rbol (libre)(libre).

(a) rbol (b) Bosque (c) Grafo

Grafos. EDA. Curso 2002/0325

rboles

Teorema: Sea G=(V,E) un g.n.d. Las siguientes afirmacionesson equivalentes:

G es un rbol (libre)Cualquier par de vrtices en G estn conectados por un nico caminosimpleG es conexo y |E|=|V|-1G es acclico pero si aadimos un arco a E, el grafo resultantecontiene un ciclo

Dem. Pg. 91-93 [Cormen,90]

Grafos. EDA. Curso 2002/0326

rboles con raz

Un rbol con razrbol con raz es un rbol con un vrtice distinguidodenominado raz.

7

3 10 4

128 211

56 1

9

Grafos. EDA. Curso 2002/0327

rbol de recubrimiento de un gnd

Un rbol de recubrimiento del grafo G=(V,E) es un rbol libreT=(V,E) tal que V=V y E EEjemplo:

a

h

b dce

g

i

f

48 7

914

1047

811

2 Peso total=37

Grafos. EDA. Curso 2002/0328

2. REPRESENTACIN DE GRAFOS

Listas de AdyacenciaListas de Adyacencia: Un grafo G=(V,E) se representa como un vectorde listas de vrtices indexado por vrtices. G[v] es una lista de los vrticesemergentes y/o incidentes de/a vV.

Memoria: O(|V|+|E|)Tiempo de acceso: O(Grado(G))

Matriz de AdyacenciasMatriz de Adyacencias: Un grafo G=(V,E) se representa como unamatriz indexada por vrtices de booleanos. La componente G[u,v] es true si(u,v)E, sino G[u,v]=false.

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

Grafos. EDA. Curso 2002/0329

Ejemplos

Grafos. EDA. Curso 2002/0330

Implementacin de grafos

Basada en listas de adyacencia:Implementacin bsica:

Grafos sin pesosVrtices numerados desde 0 hasta |V|-1

Implementacin de grafos ponderadosLa clase Arista

Los vrtices no estn numerados desde 0 hasta |V|-1Utilizacin de un diccionario (tabla hash)La clase Vertice

Grafos. EDA. Curso 2002/0331

Implementacin bsica

public class Grafo { private static final int TAMANYO_INICIAL=10; private Lista tabla []; private int numVertices; public Grafo() { numVertices=0; tabla=new Lista[TAMANYO_INICIAL]; } public void insArista (int orig, int dest) { if (tabla[orig]==null) tabla[orig]=new Lista(); tabla[orig].insertar(new Integer(dest)); } public String toString() { String s=""; for (int i=0; i

Grafos. EDA. Curso 2002/0333

Ejemplo de ejecucin

Escribe pares de vrtices separados por blancos:

1 21 42 53 53 64 25 46 6

Grafo ledo:

Orig:1 Ady= 4 2Orig:2 Ady= 5Orig:3 Ady= 6 5Orig:4 Ady= 2Orig:5 Ady= 4Orig:6 Ady= 6

Grafos. EDA. Curso 2002/0334

Ejercicio 1

Definir los siguientes mtodos en la clase Grafo:Mtodo constructor para crear el grafo a partir de la informacin dearcos leda desde un ficheroMtodo para consultar el nmero total de arcos de un grafoMtodo para consultar el grado de un vrtice dado (grado de salida si elgrafo es dirigido)Mtodo para consultar el grado del grafo (grado de salida si el grafo esdirigido)Mtodo para comprobar si el grafo est vacoMtodo para comprobar si un determinado arco pertenece al grafo

Grafos. EDA. Curso 2002/0335

Implementacin de un grafo ponderado

public class Grafo { private static final int TAMANYO_INICIAL=10; private Lista tabla []; private int numVertices; public Grafo() { numVertices=0; tabla=new Lista[TAMANYO_INICIAL]; } public void insArista (int orig, int dest, int coste) { if (tabla[orig]==null) tabla[orig]=new Lista(); tabla[orig].insertar(new Arista(dest,coste)); } public String toString() { String s=""; for (int i=0; i

Grafos. EDA. Curso 2002/0337

Implementacin de grafos en Java

La clase GrafoLa clase AristaLa clase Vrtice

GrafoEs unvectorde...

VrticesTieneunalistade...

Aristas

Grafos. EDA. Curso 2002/0338

Ejemplo:D C 10A B 12D B 23A D 87E D 43B E 11C A 19

Los nombres de los vrtices...

En general, los vrtices tendrn nombres asociados,tpicamente cadenas de caracteres:

Se mantendr una tabla hash con la codificacin de cada vrticeLos cdigos se asignan internamente con valores entre 0 y el nmero devrtices menos 1, conforme se va leyendo el grafo

D

C

A

B

E

0

1

2

3

4

DICCIONARIO

Grafos. EDA. Curso 2002/0339

La implementacin del diccionario

class ElementoHash implements Hashable {

String nombre; int codigo;

public ElementoHash (String nom) { nombre=nom; } public int hash () { return ExploracionTablaCuadratica.hash(nombre); } public boolean equals (Object x) { return nombre.equals( ((ElementoHash)x).nombre ); }}

Grafos. EDA. Curso 2002/0340

La clase Vertice

public class Vertice { String nombre; //el nombre del vrtice Lista ady; // la lista de vrtices adyacentes (aristas)

public Vertice(String v) { nombre=v; ady=new Lista(); } public String toString() { return ady.toString(); }}

Grafos. EDA. Curso 2002/0341

La clase Grafo

public class Grafo { private static final int TAMANYO_INICIAL=10; private Vertice tabla []; private int numVertices; private TablaHash diccio;

public Grafo() { ... } public insArista (String orig,String dest,int cost) { ... } public String toString() { ... }}

Grafos. EDA. Curso 2002/0342

El mtodo constructor de Grafo

public Grafo() { numVertices=0; tabla=new Vertice[TAMANYO_INICIAL]; diccio=new ExploracionTablaCuadratica();}

Grafos. EDA. Curso 2002/0343

La operacin insArista

public void insArista (String orig, String dest, int cost) { int codOrig=insNodo(orig); int codDest=insNodo(dest); Lista aux=tabla[codOrig].ady; aux.insertar(new Arista(codDest,cost)); }

Grafos. EDA. Curso 2002/0344

La codificacin de los vrtices

private int insNodo (String nomVertice) { ElementoHash aux = new ElementoHash(nomVertice); ElementoHash res; try { res= (ElementoHash) diccio.buscar(aux); return res.codigo; //Si ya est en el diccionario devolvemos su cdigo }catch (ElementoNoEncontrado e) { // Si no est, la aadimos al diccionario e incrementamos numVertices // Si fuera necesario se duplica la tabla de vrtices aux.codigo=numVertices; diccio.insertar(aux); if (numVertices==tabla.length) duplicarvectorTabla(); tabla[numVertices]=new Vertice(aux.nombre); return numVertices++; }}

Grafos. EDA. Curso 2002/0345

Ejercicio 2

Repetir el ejercicio nmero 1 sobre la implementacin completade grafo (usando el diccionario)

Grafos. EDA. Curso 2002/0346

Ejercicio 3: definir el mtodo toString en Grafo de forma que se muestrensiempre los Vrtices mediante sus etiquetas, y no con la representacin

numrica interna

public String toString() {String elGrafo =;for (int i=0;i