Tema4.3.1y2_Recorridos.pdf

EDI 2008/09 1

4.3 Exploración de grafos

l4.3.1 Recorrido en Profundidad

l4.3.2 Recorrido en Anchura

l4.3.3 Vuelta Atrás

�4.3.3.1 Esquema de la Técnica

�4.3.3.2 Ejemplos

l4.3.4 Ramificación y Poda

�4.3.4.1 Esquema de la Técnica

�4.3.4.2 Ejemplos

EDI 2008/09 2

4.3.1 Recorrido en

Profundidad

Un grafo, G, es un TAD compuesto por dos conjuntos:

� Grafos no dirigidos: V es el conjunto de vértices y A el de aristas. Cada arista está formada por un par de vértices (vi, vj)

� Grafos dirigidos: N es el conjunto de nodos y A el de arcos. Cada arco está formado por un nodo origen y un nodo destino <no, nd>

EDI 2008/09 3

4.3.1 Recorrido en

Profundidad

Tenemos un grafo, G = <V, A> y suponemos que podemos marcar un vértice como visitado.

Recorrido en profundidad � Lanza tantas llamadas recursivas como sea posible antes de volver de una llamada.

EDI 2008/09 4

4.3.1 Recorrido en

Profundidad

Pasos del Algoritmo:

� Pto. de partida v � V, lo marcamos como visitado.

� Si � w � V no visitado y adyacente a v, lo tomamos como pto. de partida y lanzamos recursivamente el algoritmo.

� Si al regresar de la recursión � x � V no visitado y adyacente a v, hacemos lo mismo que en el pto. 2.

� Si � y � V que no ha sido visitado, hacemos lo mismo que en el pto. 2.

� Terminamos cuando � v � V se han visitado.

EDI 2008/09 5

4.3.1 Recorrido en

Profundidad

2

43

5

1

7

89

6

EDI 2008/09 6

4.3.1 Recorrido en

Profundidad

2

43

5

1

7

89

6

Adyacentes a 1: 2, 4, 8

Recorrido: 1, 2

EDI 2008/09 7

4.3.1 Recorrido en

Profundidad

2

43

5

1

7

89

6


Recorrido: 1, 2, 3

EDI 2008/09 8

4.3.1 Recorrido en

Profundidad

2

43

5

1

7

89

6


Recorrido: 1, 2, 3 , 4

EDI 2008/09 9

4.3.1 Recorrido en

Profundidad

2

43

5

1

7

89

6

Adyacentes a 4: 1, 2, 3, 7

Recorrido: 1, 2, 3, 4 , 7

EDI 2008/09 10

4.3.1 Recorrido en

Profundidad

2

43

5

1

7

89

6


Recorrido: 1, 2, 3, 4, 7, 6

EDI 2008/09 11

4.3.1 Recorrido en

Profundidad

2

43

5

1

7

89

6

Adyacentes a 6: 5, 7

Recorrido: 1, 2, 3, 4, 7, 6, 5

EDI 2008/09 12

4.3.1 Recorrido en

Profundidad

2

43

5

1

7

89

6


Recorrido: 1, 2, 3, 4, 7, 6, 5

EDI 2008/09 13

4.3.1 Recorrido en

Profundidad

2

43

5

1

7

89

6


Recorrido: 1, 2, 3, 4, 7, 6, 5

EDI 2008/09 14

4.3.1 Recorrido en

Profundidad

2

43

5

1

7

89

6


Recorrido: 1, 2, 3, 4, 7, 6, 5 , 9

EDI 2008/09 15

4.3.1 Recorrido en

Profundidad

2

43

5

1

7

89

6


Recorrido: 1, 2, 3, 4, 7, 6, 5, 9 , 8

EDI 2008/09 16

4.3.1 Recorrido en

Profundidadprocedimiento recorrido_en_profundidad (G: grafo)

para cada v � N hacermarca[v] � no visitado

fpara

para cada v � N hacersi marca[v] � visitado entonces

rp(G, marca, v)fsi

fpara

fprocedimiento

procedimiento rp (G: grafo; marca:vector[1..n]; v: nodo){El nodo v no ha sido visitado anteriormente}

marca[v] � visitadopara cada nodo adyacente a v hacersi marca[w] � visitado entonces

rp(G, marca, w)fsi

fpara

fprocedimiento

EDI 2008/09 17

4.3.1 Recorrido en

Profundidad

PROCEDURE RecorreProfundidad (g: TGrafo);VAR n: integer; nodo: TNodo; marca: TVisitado; c: TipoConjuntoNodos;BEGIN DameNodos(g, c);{TAD grafo} n:= Cardinal(c); {TAD Conjunto} InicializarVisitados(marca, n); {TAD TVisitado} WHILE NOT EsConjuntoVacio(c) DO BEGIN DameNodo(c, nodo); {TAD Conjunto} Quitar(c, nodo);{TAD Conjunto} IF NOT EsVisitado(marca,nodo) THEN {TAD TVisitado} rp(g, nodo, marca);END;

EDI 2008/09 18

4.3.1 Recorrido en

Profundidad

PROCEDURE rp(g:TGrafo; nodos:TNodo; VAR marca:TVisitado);{El nodo n no ha sido visitado anteriormente}VAR i, k: integer; adya: TipoConjuntoNodos;BEGIN MarcarVisitado(marca,n); {TAD TVisitado} Adyacentes(g,adya,n);{TAD grafo, devuelve los adyacentes a n} WHILE NOT EsConjuntoVacio(adya) DO BEGIN DameNodo(adya, nodo); {TAD Conjunto} Quitar(adya, nodo); {TAD Conjunto} IF PerteneceConjuntoNodos(adya,nodo) AND NOT EsVisitado(marca,i) THEN rp(g, marca, nodo); END;END;

EDI 2008/09 19

4.3.1 Recorrido en

Profundidad

Complejidad:�Cada nodo se visita 1 vez � n llamadas a rp � �(n)

�Examinamos todas las aristas � �(a)

�Por tanto podemos concluir que �(max(n,a))

EDI 2008/09 20

4.3.1 Recorrido en

Profundidad

lEl recorrido en profundidad de un grafo conexo, G, crea un árbol de recubrimiento T:� Las aristas de T � aristas de G empleadas en el recorrido en

profundidad.

� La raíz de T � punto de partida de la exploración de G

lSi el grafo no es conexo, tendremos un árbol de recubrimiento por cada componente conexa.

lLa exploración en profundidad de un grafo nos permite �numerar� los nodos del grafo en �preorden�.

EDI 2008/09 21

4.3.1 Recorrido en

Profundidad

1

2 3 4

5 6 7 8

Ejem plo: recorrido en profundidad del siguiente grafo no dirigido

EDI 2008/09 22

4.3.1 Recorrido en

Profundidad

1

2 3 4

5 6 7 8

Secuencia de llamadas a rp:

1. rp(1) {llamada inicial}2. rp(2) {llam. rec.}3. rp(3) {llam. rec.}4. rp(6) {llam. rec}5. rp(5) {llam. rec. no se puede continuar}6. rp(4) {llam. adyacente al nodo 1}7. rp(7) {llam. rec}8. rp(8) {llam. rec. no se puede continuar}

EDI 2008/09 23

4.3.1 Recorrido en

Profundidad

Árbol de recorrido en profundidad (T):

1

2 3 4

5 6 7 8

EDI 2008/09 24

4.3.1 Recorrido en

Profundidad

lPuntos de articulación: un vértice v de un grafo conexo es un punto de articulación si el subgrafo que se obtiene de eliminar v y todas las aristas incidentes en v ya no es conexo.

lGrafo biconexo (o no articulado): aquel grafo conexo que no tiene puntos de articulación.

lGrafo bicoherente (o 2-arista conexo): aquel grafo cuyos puntos de articulación están unidos a cada componente del subgrafo restante por, al menos, dos aristas.

EDI 2008/09 25

4.3.1 Recorrido en

Profundidad

lSi el grafo representa un sistema de comunicaciones:

�Que dicho grafo sea biconexo nos asegura el correcto funcionamiento de la red aunque falle el equipo de uno de los nodos.

�Que dicho grafo sea bicoherente nos asegura el correcto funcionamiento de la red aunque falle una línea de transmisión.

EDI 2008/09 26

4.3.1 Recorrido en

Profundidad

lCálculo de puntos de articulación: lpreNum[v]: es el número asignado a cada vértice v

en el recorrido en profundidad del grafo (recorrido en preorden del árbol).

lmasAlto[v]: sea w el nodo más alto del árbol que se puede alcanzar desde v siguiendo cualquier número de lineas contínuas y subiendo por una línea discontínua como máximo. Entonces, se define masAlto[v] como preNum[w].

EDI 2008/09 27

4.3.1 Recorrido en

Profundidad

Cálculo de puntos de articulación:

1

2 3 4

5 6 7 8

� A la izquierda de cada vértice v se representa preNum[v]� A la derecha de cada vértice v se representa masAlto[v]

EDI 2008/09 28

4.3.1 Recorrido en

Profundidad

lCálculo de puntos de articulación: lSea v cualquier nodo del árbol excepto la raíz y x un

hijo de v:�Si masAlto[x]<preNum[v] se puede llegar desde x a

regiones más altas del grafo sin pasar por la arista (v,x), luego v no es punto de articulación.

�Si masAlto[x]�preNum[v] no se puede llegar desde x a regiones más altas del grafo sin pasar por la arista (v,x), luego v es punto de articulación.

lSi v es la raíz del árbol y tiene más de un hijo, es punto de articulación.

EDI 2008/09 29

4.3.1 Recorrido en

Profundidad

Procedimiento para el cálculo de puntos de articulación:

� Efectuar un recorrido en profundidad de G, generando un arbol T y calculando preNum[v].

� Recorrer T en postorden. Calcular masAlto[v] como el mínimo de:� preNum[v]� preNum[w] para todo w tal que haya una arista (v,w) en G que

no esté en T.� masAlto[x] para todo hijo x de v.

� Calcular los puntos de articulación de G:� la raíz es punto de articulación si y solo si tiene más de un hijo� Cualquier otro nodo v es punto de articulación si y solo si tiene

un hijo x tal que masAlto[x] � preNum[v].

EDI 2008/09 30

4.3.1 Recorrido en

Profundidad

lSi G={N,A} es dirigido:

�El algoritmo de recorrido en profundidad es esencialmente el mismo

�Con la salvedad de que hay que redefinir la interpretación de la palabra �adyacente�

lEn un grafo dirigido, el nodo w es adyacente a otro nodo v si existe la arista dirigida <v,w>.

lSi existe <v,w> pero no existe <w,v>, w es adyacente a v pero v no es adyacente a w.

EDI 2008/09 31

4.3.1 Recorrido en

Profundidad

Ejem plo: recorrido en profundidad del siguiente grafo dirigido

EDI 2008/09 32

4.3.1 Recorrido en

Profundidad

Secuencia de llamadas a rp:

1. rp(1) {llamada inicial}2. rp(2) {llam. rec.}3. rp(3) {llam. rec. no se puede continuar}4. rp(4) {llam. adyacente al nodo 1}5. rp(8) {llam. rec.}6. rp(7) {llam. rec. no se puede continuar}7. rp(5) {nuevo punto de comienzo}8. rp(6) {llam. rec. no se puede continuar}

EDI 2008/09 33

4.3.1 Recorrido en

Profundidad

Bosque de recorrido en profundidad:

EDI 2008/09 34

4.3.2 Recorrido en Anchura

Un grafo, G, es un TAD compuesto por dos conjuntos:

� Grafos no dirigidos: V es el conjunto de vértices y A el de aristas. Cada arista está formada por un par de vértices, (vi, vj)

� Grafos dirigidos: N es el conjunto de nodos y A el de arcos. Cada arco está formado por un nodo origen y un nodo destino <no, nd>

EDI 2008/09 35


Tenemos un grafo, G = <V, A> y suponemos que podemos marcar un nodo como visitado.

Recorrido en anchura � visita todos los vecinos de un nodo antes de avanzar.

El recorrido en anchura no es recursivo.

EDI 2008/09 36


Pasos del Algoritmo:

� Pto. de partida v � V, lo marcamos como visitado.

� � w � V no visitado y adyacente a v, lo

visitamos.

� Visitamos todos los nodos adyacentes a los nodos w visitados en el paso anterior que aún no hayan sido visitados.

� Terminamos cuando � v � V se han visitado.

EDI 2008/09 37


2

43

5

1

7

89

6


Recorrido: 1, 2, 4, 8

EDI 2008/09 38


2

43

5

1

7

89

6


Recorrido: 1, 2, 4, 8 , 3

EDI 2008/09 39


2

43

5

1

7

89

6

Adyacentes a 4: 1, 2, 3, 7

Recorrido: 1, 2, 4, 8, 3, 7

EDI 2008/09 40


2

43

5

1

7

89

6


Recorrido: 1, 2, 4, 8, 3, 7, 9

EDI 2008/09 41


2

43

5

1

7

89

6


Recorrido: 1, 2, 4, 8, 3, 7, 9 , 5

EDI 2008/09 42


2

43

5

1

7

89

6


Recorrido: 1, 2, 4, 8, 3, 7, 9, 5 , 6

EDI 2008/09 43


procedimiento recorrido(G)

para cada v � N hacer

marca[v] � no visitado

fpara

para cada v � N hacer

si marca[v] � visitado entonces

ra(v)

fsi

fpara

fprocedimiento

procedimiento ra(v)

Q � colavacia

marca[v] � visitado

poner v en Q

mientras Q no esté vacía hacer

quitar aux de Q

para todo w adyacente a aux hacer

si marca[w] � visitado entonces

marca[w] � visitado

poner w en Q

fsi

fpara

fmientras

fprocedimiento

EDI 2008/09 44


lEl tiempo requerido para realizar un recorrido en anchura de un grafo es el mismo que para un recorrido en profundidad � � (max(n,a))

lTambién genera árboles de recubrimiento. Si el grafo es conexo � un único árbol.

lSe emplea en exploraciones parciales de grafos, para hallar el camino más corto entre dos puntos de un grafo, etc.

EDI 2008/09 45


PROCEDURE RecorreAnchura(g: TGrafo);VAR n: integer; nodo: TNodo; marca: TVisitado; c: TipoConjuntoNodos;BEGIN DameNodos(g, c);{TAD grafo} n:= Cardinal(c); {TAD Conjunto} InicializarVisitados(marca, n); {TAD TVisitado} WHILE NOT EsConjuntoVacio(c) DO BEGIN DameNodo(c, nodo); {TAD Conjunto} Quitar(c, nodo);{TAD Conjunto} IF NOT EsVisitado(marca,nodo) THEN {TAD TVisitado} ra(g, nodo, marca);END;

EDI 2008/09 46

4.3.2 Recorrido en AnchuraPROCEDURE ra(g:TGrafo; nodo: TNodo; VAR marca:TVisitado);VAR q: TCola;

w, v: TNodo;adya: TipoConjuntoNodo;

BEGIN CrearColaVacia(q); MarcarVisitado(marca,nodo); {TAD TVisitado} Insertar(q,nodo); WHILE NOT EsColaVacia(q) DO BEGIN Desencolar(q, w); Adyacentes(g, w, adya); {TAD grafo} WHILE NOT EsConjuntoVacio(adya) DO BEGIN DameNodo(adya, v); {TAD Conjunto} Quitar(adya, v); {TAD Conjunto} IF NOT EsVisitado(marca,v) THEN BEGIN MarcarVisitado(marca,v); {TAD TVisitado} Encolar(q,v); END; END; END;END;

EDI 2008/09 47


1

2 3 4

5 6 7 8

Ejem plo: recorrido en anchura del siguiente grafo no dirigido

EDI 2008/09 48


1

2 3 4

5 6 7 8

Ejemplo: recorrido en anchura

Paso Nodo Visitado Q1 1 2, 3, 42 2 3, 4, 5, 63 3 4, 5, 64 4 5, 6, 7, 85 5 6, 7, 86 6 7, 87 7 88 8 -

EDI 2008/09 49


Árbol de recorrido en anchura:

1

2 3 4

5 6 7 8

EDI 2008/09 50


EjemplolSe nos da:

�El valor inicial 1

�Las operaciones x2 y 3 ( es división entera)

lEl objetivo es construir otros valores. Por ejemplo: 10 = 1 x 2 x 2 x 2 x 2 3 x 2

lSe desea construir un valor concreto n:�Búsqueda en un grafo infinito

�Un recorrido en profundidad podría no funcionar

�Un recorrido en anchura es la mejor solución

EDI 2008/09 51


2

1

8

4

16

5

32

10

64

21

128

3

20

6 12

40

13

80

42

256

7

85

512

14

84

........

Documents

Tema4.3.1y2_Recorridos.pdf