b
t
c
45
1
3
10
25
40
55
30
25
50
20
3
15
Recorridos en grafos
Recorridos
Indice
Introduccin.
Bsqueda primero en profundidad.
Bsqueda primero en anchura.
Usos de los recorridos.
Digrafos acclicos.
Orden topolgico.
Recorridos
Introduccin
Recorridos
Recorrido: procedimiento sistemtico de
exploracin de un grafo mediante el examen
de todos sus vrtices y aristas.
Un recorrido es eficiente si visita todos los
vrtices y aristas en un tiempo proporcional a
su nmero, esto es, en tiempo lineal.
Bsqueda primero en profundidad
Analoga: deambular en un laberinto con una
cuerda y un bote de pintura, para no perderse.
Se selecciona un vrtice inicial s de G, al que se fija un extremo de
la cuerda y se pinta s como "visitado". Se asigna s a u (vrtice en
curso).
Se recorre G considerando una arista arbitraria (u, v). Si la arista (u,
v) conduce a una vrtice v ya visitado se retorna inmediatamente al
vrtice u.
Si (u, v) conduce a un vrtice no visitado v, entonces se extiende la
cuerda y se fija en v. Se pinta v como "visitado" y se asigna a u
(vrtice en curso), repitiendo el mismo procedimiento anterior.
Si todas las aristas incidentes a un vrtice conducen a vrtices ya
visitados, se enrolla la cuerda vuelta atrs a la arista que condujo a
u y se repite el procedimiento anterior para las aristas incidentes que
no se han recorrido antes.
El proceso termina cuando la vuelta atrs conduce al vrtice inicial s
y no hay ms aristas incidentes sin explorar desde s.
Recorridos
Bsqueda primero en profundidad
Animacin
a
b
c
c
d
Recorridos
c
e
c
e
e
5
Bsqueda primero en profundidad
El recorrido BPP es una generalizacin del recorrido
preorden de un rbol.
Se pueden identificar cuatro tipos de aristas durante el
recorrido:
Aristas de descubrimiento: son aquellas aristas que conducen al
descubrimiento de nuevos vrtices. Tambin se les llama aristas de
rbol.
Aristas de retorno: son las aristas que conducen a vrtices
antecesores ya visitados en el rbol.
Aristas de avance: son las aristas que conducen a vrtices
descendientes en el rbol.
Aristas de cruce: son aristas que conducen a un vrtice que no es
ancestro de otro o a vrtices que estn en diferentes rboles.
Las aristas de descubrimiento forman un rbol de
cubrimiento de los componentes conectados del vrtice
inicial s.
Recorridos
Algoritmo recursivo BPP
recorre_grafo_bpp()
{
for cada vrtice v
marca[v]=SINVISITAR;
for cada vrtice v
if (marca[v]==SINVISITAR)
BPP(v);
}
BPP(u)
{
marca[u]=VISITADO;
for cada vrtice v adyacente a u
if (marca[v]==SINVISITAR)
BPP(v);
}
Orden de complejidad del recorrido en profundidad:
Con lista de adyacencia, se recorre cada elemento de lista una
vez, O(n + e).
Con matriz de adyacencia, para cada nodo se buscan sus
adyacentes, O(n2).
Recorridos
Algoritmo recursivo BPP
Recorridos
Applet de animacin del recorrido BPP
Bsqueda primero en anchura
Analoga: deambular en un laberinto con una
cuerda y un bote de pintura, para no perderse.
Se selecciona un vrtice inicial s de G, al que se fija inicialmente
un extremo de la cuerda y se marca s con el nivel 0.
Se ajusta la longitud de la cuerda igual al de una arista. Se
visitan y marcan con 1 todos los vrtices adyacentes a s que se
alcanzan con esa longitud.
Se repite el proceso anterior con una longitud de cuerda igual al
de dos aristas. Todos los vrtices adyacentes al nivel 1 se
marcan con el nivel 2.
El recorrido termina cuando todos los vrtices tienen asignado
un nivel.
Recorridos
Bsqueda primero en anchura
Animacin
0
b
1
c
d
e
0
b
1
c
1
Recorridos
10
Bsqueda primero en anchura
El recorrido BPA es una generalizacin del recorrido por
niveles de un rbol.
Se pueden identificar dos tipos de aristas durante el
recorrido:
Aristas de descubrimiento: son aquellas aristas que conducen al
descubrimiento de nuevos vrtices.
Aristas de cruce: son aristas que conducen a un vrtice ya
visitado.
Las aristas de descubrimiento forman un rbol de
cubrimiento de los componentes conectados del vrtice
inicial s.
Recorridos
11
Algoritmo BPA
recorre_grafo_bpa()
{
for cada vrtice v
marca[v]=SINVISITAR;
for cada vrtice v
if (marca[v]==SINVISITAR)
BPA(v);
}
BPA(v)
{
marca[v] = VISITADO;
InsertaCola(v, C)
while not EsVacaCola(C) {
u = SuprimirCola(C);
for cada nodo y adyacente a u {
if (marca[y]==SINVISITAR) {
marca[y] = VISITADO;
InsertaCola(y, C);
}
}
}
}
Orden de complejidad del recorrido en anchura:
Con lista de adyacencia: O(n + e).
2
Recorridos Con matriz de adyacencia: O(n ).
12
Recorrido BPA
Recorridos
Applet de animacin del recorrido BPA
13
Usos de los Recorridos
Ambos recorridos se pueden usar para resolver los siguientes problemas:
Probar que G es conectado.
Obtener un rbol de expansin de G.
Obtener los componentes conectados de G.
Obtener un camino entre dos vrtices dados de G, o indicar que no existe tal camino.
El recorrido BPP se usa para:
Obtener un ciclo en G, o indicar que G no tiene ciclos.
El recorrido BPA se usa para:
Obtener para cada vrtice v de G, el nmero mnimo de aristas de cualquier camino entre s y v.
Recorridos
14
Digrafos acclicos
Es un grafo dirigido que no tiene ciclos.
Representan relaciones ms generales que los
rboles pero menos generales que los digrafos.
Ejemplo: representar estructuras sintcticas de
expresiones aritmticas con subexpresiones
comunes y el orden parcial de un conjunto.
*
+
a
Recorridos
+
b
Orden parcial R en un conjunto
S, relacin binaria que cumple:
elemento a de S, (a R a)
es falso.
a, b, c de S, si (a R b) y
(b R c) entonces (a R c).
(a+b)*(d+d*(a+b))
15
Digrafos acclicos
Un grafo es acclico si durante un recorrido BPP no
existen aristas de vuelta atrs o retorno.
Algoritmo: recorrer el digrafo usando BPP y
numerando los nodos nuevos en el recorrido. Si en
algn momento en una arista de retorno un nodo
descendiente tiene un nivel de profundidad menor
que el antecesor, entonces existe un ciclo.
1
2
3
Recorridos
arista de retorno
5
7
16
Orden topolgico
Ordenamiento topolgico de un digrafo acclico: orden lineal de los vrtices colocndolos a lo largo
de una lnea horizontal de tal manera que todas las aristas tengan una direccin de izquierda a
derecha.
Ejemplo: las tareas de un proyecto de construccin.
Algoritmo: usar una versin modificada de BPP.
orden_topologico(v)
/* orden inverso */
{
marca[v]=VISITADO;
for cada vrtice w en lista_adyacencia(v)
if (marca[w]==SINVISITAR)
orden_topologico(w);
imprime(v);
}
Recorridos
17
Orden topolgico
Ejemplo
1
Recorridos
Orden topolgico:
123456
132456
215346
18
Indice
1. Introduccin.
2. Definiciones.
3. Recorridos en grafos.
4. Algoritmos de caminos ms cortos.
5. rbol de cubrimiento de costo mnimo.
6. Flujo en redes. Flujo mximo.
Recorridos
19
