ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
NIVEL 17: ESTRUCTURAS NO LINEALES
Recorridos y Algorítmica de Grafos
1
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Agenda
• Recorridos de grafos
• Recorridos Planos
• Recorridos en profundidad
• Recorridos por niveles
• Recorridos Heurísticos
• Algorítmica de grafos
• Camino Hamilton
• Camino Euler
2
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido de grafos
• ¿Cómo pasar exactamente una vez por cada uno de los vértices de la estructura?
• Los grafos se pueden recorrer de diferentes formas con el fin de determinar alguna característica o encontrar alguna información especial.
3
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido de grafos
• Tipos de recorrido:
• Plano
• En profundidad
• Por niveles
• En ambas direcciones
4
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido de grafos• Recorrido plano
• Recorrido en profundidad
• Recorrido por niveles
• Recorrido en ambas direcciones
5
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Agenda
• Recorridos de grafos
• Recorridos Planos
• Recorridos en profundidad
• Recorridos por niveles
• Recorridos Heurísticos
• Algorítmica de grafos
• Camino Hamilton
• Camino Euler
6
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido plano
• El más sencillo
• Barrido secuencial de los elementos del conjunto V.
• Permite localizar todos los vértices que cumplan con alguna propiedad, sin tener en cuenta la topología (ignora los arcos).
7
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido plano
• ¿Cómo se hace en Cupi2Collections?
1. Pedir los elementos (valores) a la tabla de hashing (es una Collection).
2. Recorrerla.
8
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido plano
1. Pedir los elementos (valores) a la tabla de hashing (es una Collection).
9
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido plano
2. Recorrerla.
10
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido plano
• Ejercicio
• Retornar todos los sumideros de un grafo dirigido, usando un recorrido plano.
11
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Agenda
• Recorridos de grafos
• Recorridos Planos
• Recorridos en profundidad
• Recorridos por niveles
• Recorridos Heurísticos
• Algorítmica de grafos
• Camino Hamilton
• Camino Euler
12
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido en profundidad
• Equivalente a un recorrido en preorden de un árbol n-ario:
• Primero el vértice
• Después sus sucesores
+• Verificando en TODO momento que el algoritmo no se quede en ciclos
13
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido en profundidad
• Consta de dos rutinas:
1. Rutina 1: Hace un recorrido en profundidad a partir de un vértice dado, marcando los puntos por los cuales va pasando.
2. Rutina 2: Busca vértices sin marcar y lanza la rutina 1. Termina cuando TODOS los vértices hayan sido visitados.
14
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido en profundidad
15
1
7
5
2
6
3
4
1
1, 7
Se visita el vértice 1, se marca, se localizan sus sucesores y se hace una llamada recursiva sobre cada uno de ellos, verificando que no estén marcados
Se hace el recorrido en profundidad partiendo del vértice 7 (el único sucesor de 1).
1
7
5
2
6
3
4
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido en profundidad
16
1
7
5
2
6
3
4
1, 7, 5
1, 7, 5, 2
Se hace el recorrido en profundidad a partir del vértice 5. Al terminar TODO este recorrido, se debe comenzar el mismo proceso a partir del vértice 6.
Pendiente recorrido desde: 6
Se repite recursivamente el proceso para los vértices 2 y 6 (sucesores de 5).
Pendiente recorrido desde: 6,6
1
7
5
2
6
3
4
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido en profundidad
17
1
7
5
2
6
3
4
1, 7, 5, 2, 3
1, 7, 5, 2, 3, 6
Se recorre en profundidad el grafo a partir del vértice 3 (sucesor de 2).
Pendiente recorrido desde: 6,6
Se repite recursivamente el proceso para los vértices 4 y 6 (sucesores de 3).
Pendiente recorrido desde: 6,6,4
1
7
5
2
6
3
4
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido en profundidad
18
1
7
5
2
6
3
4
1, 7, 5, 2, 3, 6, 4
Puesto que el vértice 4 no tiene sucesores, se hace un recorrido en profundidad desde el elemento 6 (el último que quedó pendiente en el proceso)
Pendiente recorrido desde: 6,6
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido en profundidad
• Se puede observar que el orden de visita de los elementos depende de:
• El vértice inicial escogido.
• El orden en el cual se retornen los sucesores de un vértice.
19
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido en profundidad
• Ejercicio:• Dibujar la secuencia de recorrido en profundidad en
el siguiente caso:
20
Arrancando en el vértice 3
1
7
5
2
6
3
4
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido en profundidad
Ejercicio:
• Escribir el método Iterador<Vertice<K, V, A>> darRecorridoProfundidad(
) que retorna un iterador con los vértices visitados por profundidad.
• ¿En qué clase(s) va este método?
21
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido en profundidad• Clase Grafo
• Se crea el iterador donde se va a hacer la acumulación de parámetros (recorrido)
22
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido en profundidad
• Clase Grafo
• Rutina 2: Busca vértices sin marcar y lanza la rutina 1. Termina cuando TODOS los vértices hayan sido visitados.
23
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido en profundidad• Clase Grafo
• Retorna el iterador lleno.
24
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido en profundidad• Clase Vertice
• El vértice se añade al iterador.
25
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido en profundidad• Clase Vertice
• El vértice se marca
26
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido en profundidad
• Clase Vertice
• Recorre todos sus sucesores
27
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido en profundidad
• Clase Vertice• Si el sucesor NO está marcado, lanza recursivamente el
recorrido en profundidad a partir del sucesor
28
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Agenda
• Recorridos de grafos
• Recorridos Planos
• Recorridos en profundidad
• Recorridos por niveles
• Recorridos Heurísticos
• Algorítmica de grafos
• Camino Hamilton
• Camino Euler
29
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido por niveles
• Similar al proceso correspondiente en un árbol n-ario.
• Consta de dos rutinas:
1. Rutina 1: Hace un recorrido por niveles a partir de un vértice dado, marcando los puntos por los cuales va pasando.
2. Rutina 2: Busca vértices sin marcar y lanza la rutina 1. Termina cuando TODOS los vértices hayan sido visitados.
30
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido por niveles
• La lista de elementos para ser recorridos se denomina frente de exploración.
31
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido por niveles
32
1
7
5
2
6
3
4
Se visita el vértice 1, se marca, se localizan sus sucesores y se incluyen al final del frente de exploración.
Recorrido: 1Frente de Exploración: 7
Se toma el primer elemento del frente de exploración (7) y se procesa como en el paso anterior.
Recorrido: 1, 7Frente de Exploración: 5, 6
1
7
5
2
6
3
4
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido por niveles
33
1
7
5
2
6
3
4
Recorrido: 1, 7, 5Frente de Exploración: 6, 2, 6
Recorrido: 1, 7, 5, 6Frente de Exploración: 2, 6, 4
1
7
5
2
6
3
4
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido por niveles
34
1
7
5
2
6
3
4
Recorrido: 1, 7, 5, 6, 2Frente de Exploración: 6, 4, 3
Recorrido: 1, 7, 5, 6, 2, 4Frente de Exploración: 3
1
7
5
2
6
3
4
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido por niveles
35
1
7
5
2
6
3
4
Recorrido: 1, 7, 5, 6, 2Frente de Exploración: 6, 4, 3
Recorrido: 1, 7, 5, 6, 2, 4Frente de Exploración: 3
1
7
5
2
6
3
4
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido por niveles
36
1
7
5
2
6
3
4
Recorrido: 1, 7, 5, 6, 2, 3Frente de Exploración:
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido por niveles
Ejercicio:
• Escribir el método Iterador<Vertice<K, V, A>> darRecorridoNiveles( ) que retorna un iterador con los vértices visitados por niveles.
• ¿En qué clase(s) va este método?
37
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido por niveles• Clase Vertice
• Se crea el iterador a retornar con los vértices recorridos por niveles
38
…
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido por niveles• Clase Vertice
• Se crea una cola para guardar el frente de exploración
39
…
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido por niveles• Clase Vertice
• Se recorren todos los vértices del grafo
40
…
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido por niveles• Clase Vertice
• Se verifica que el vértice no esté marcado, es decir que no ha sido visitado
41
…
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido por niveles• Clase Vertice
• Se inserta el vértice en el frente de exploración
42
…
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido por niveles• Clase Vertice
• Para cada vértice del frente de exploración …
43
…
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido por niveles• Clase Vertice
• Se toma el vértice
44
…
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido por niveles• Clase Vertice
• Si no ha sido marcado …
45
…
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido por niveles• Clase Vertice
• Se marca
46
…
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido por niveles• Clase Vertice
• Se añade al iterador
47
…
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido por niveles• Clase Vertice
• Cada uno de sus sucesores …
48
…
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido por niveles• Clase Vertice
• Se añade al frente de exploración si no ha sido previamente marcado
49
…
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorrido por niveles• Clase Vertice
• Se retorna el iterador
50
…
…
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Agenda
• Recorridos de grafos
• Recorridos Planos
• Recorridos en profundidad
• Recorridos por niveles
• Recorridos Heurísticos
• Algorítmica de grafos
• Camino Hamilton
• Camino Euler
51
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorridos heurísticos
• Son informados:
• Tienen en cuenta alguna característica del mundo en el cual ocurre el problema.
• El proceso de avance es más “inteligente”.
• Dan al algoritmo de búsqueda del camino, una medida de qué tan cerca se encuentra de una solución:
• En la exploración, dan prioridad a los vértices que tengan más posibilidades de llevar a la respuesta.
• Se usan como técnicas de inteligencia artificial en juegos, robótica, …
52
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Recorridos heurísticos
• El frente de búsqueda se encuentra ordenado de acuerdo con una función h(v):
• Un vértice tiene un menor valor a medida que se encuentra más cerca de la respuesta.
• h(v) es una heurística y depende del problema mismo sobre el cual se está trabajando.
53
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Ejemplo
• Recorrido heurístico
54
2 28 3
1 6 4
7 5
8 3
1 6 4
7 5
2 8 3
1 6 4
7 5
2 8
1 4
3
7 6 5
....
1 2 3
4 5 6
7 8
2 8 3
1 6
7 5 4
2 8 3
1 6
7 5 4
2 8
1 6 3
7 5 4
...
...
...
...
...
...
........
...
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Agenda
• Recorridos de grafos
• Recorridos Planos
• Recorridos en profundidad
• Recorridos por niveles
• Recorridos Heurísticos
• Algorítmica de grafos compleja
• Camino Hamilton
• Camino Euler
55
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Camino Hamilton
56
El camino Hamilton pasa una vez por TODOS los vértices
/**
* Indica si en el grafo hay camino hamiltoniano
* @return true si hay camino hamiltoniano o false en caso contrario
*/
public boolean hayCaminoHamilton( )
{
// Recorre todos los vértices del grafo buscando un camino de Hamilton
for( Vertice<K, V, A> vertice : vertices.values( ) )
{
// Borra todas las marcas presentes en el grafo
reiniciarMarcas( );
if( vertice.hayCaminoHamilton( 0, darOrden( ) ) )
return true;
}
return false;
}
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Camino Hamilton
57
/**
* Indica si hay un camino de Hamilton que pasa por el vértice actual,
* teniendo en cuenta que en dicho camino ya se ha pasado por un cierto
* número de vértice (longActual) y que debe pasar por todos lo vértices
* del grafo (ordenGrafo)
* @param longActual Longitud actual del camino
* @param ordenGrafo Orden del grafo
* @return True si existe, False si no
*/
public boolean hayCaminoHamilton( int longActual, int ordenGrafo )
{
longActual++;
if( longActual == ordenGrafo )
return true;
else {
marcar( );
for( Arco<K, V, A> arco : darSucesores( ) )
{
Vertice<K, V, A> vert = arco.darVerticeDestino( );
if( !vert.marcado( ) && vert.hayCaminoHamilton( longActual, ordenGrafo ) )
{
return true;
}
}
}
return false;
}
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Agenda
• Recorridos de grafos
• Recorridos Planos
• Recorridos en profundidad
• Recorridos por niveles
• Recorridos Heurísticos
• Matrices de adyacencias
• Algorítmica de grafos
• Camino Hamilton
• Camino Euler• Árboles de recubrimiento
58
ISIS1206 – Estructuras de Datos
http://cupi2.uniandes.edu.co
Camino Euler
59
El camino Euler pasa una vez por TODOS los arcos