RECORRIDOS EN GRAFOS
Asignación de la semana
• Escriba un programa en C++ que permita:
– Leer la información de un grafo ponderado , de N
nodos (N<=20)
• El valor almacenado en cada nodo es UN numero
entero
– Para DOS nodos dados, determinar si existe un
camino entre ellos y cual es su valor.
• Desarrollo en parejas
• Fecha limite de entrega: Martes 22 de octubre 11:59
Investigar
• Algoritmos de recorrido en un grafo:
– Primero en Anchura
– Primero en Profundidad
Recorridos de un Grafo
• Se manejan 2 algoritmos básicos
• Estos algoritmos se deben apoyar en estructuras de
datos auxiliares.
– RECORRIDO PRIMERO EN ANCHURA
• También llamado BUSQUEDA EN ANCHURA o Breadth First
Search
• Utiliza una cola auxiliar
– RECORRIDO PRIMERO EN PROFUNDIDAD
• También llamado BUSQUEDA EN PROFUNDIDAD o Depth
First Search
• Utiliza una pila auxiliar
Recorrido
Primero en Profundidad
• Depth First Search
• algoritmo que permite recorrer todos los nodos de un grafo.
• Es una generalización del recorrido pre orden de un árbol.
• Se parte partir de un vértice determinado v y a partir de alli,
cuando se visita un nuevo vértice, explorar cada camino que
salga de él.
• Hasta que no se haya finalizado de explorar uno de los
caminos no se comienza con el siguiente. Un camino deja de
explorarse cuando se llega a un vértice ya visitado.
Recorrido
Primero en Profundidad
http://163.10.22.82/OAS/recorrido_grafos/dfs__recorrido_en_profundidad.html
Depth Fisrt Search
• Se plantea el algoritmo siguiendo un esquema recursivo:
• dado G = (V , E)
1. Marcar todos los vértices como no visitados.
2. Elegir vértice u como punto de partida.
3. Marcar u como visitado.
4. Para todo v adyacente a u,(u,v) Є E,
Si v no ha sido visitado,
llamar recursivamente para ejecutar (3) y (4)
para v.
• Finalizar cuando se hayan visitado todos los nodos alcanzables
desde u.
• Si desde u no fueran alcanzables todos los nodos del grafo:
– volver a (2),
– elegir un nuevo vértice de partida v no visitado,
– repetir el proceso hasta que se hayan recorrido todos los
vértices.
Depth Fisrt Search
• main_dfs (grafo)
– inicializar marca en false (arreglo de booleanos);
– para cada vértice v del grafo
• si (marca[v] == noVisitado) -> dfs(v);
• dfs (v: vértice)
– marca[v]:= visitado;
– para cada nodo w adyacente a v
• si (marca[w] == noVisitado) -> dfs(w);
Recorrido Primero en anchura
• Breadth First Search.
• Es otra forma sistemática de visitar los vértices.
• Se denomina en anchura porque desde cada vértice v
que se visita se busca en forma tan amplia como sea
posible, visitando todos los vértices adyacentes a v.
• Es una generalización del recorrido por niveles de un
árbol.
• La estrategia ES:
– Se parte de algún vértice u, visitar u y, después, visitar
cada uno de los vértices adyacentes a u.
– Hay que repetir el proceso para cada nodo adyacente
a u, siguiendo el orden en que fueron visitados.
Recorrido Primero en anchura
http://163.10.22.82/OAS/recorrido_grafos/bfs__recorrido_en_amplitud.html
Recorrido Primero en anchura
• Se plantea el algoritmo siguiendo un esquema iterativo:
dado G = (V , E) y teniendo en cuenta que el vértice
origen es u.
1. Encolar el vértice origen u.
2. Marcar el vértice u como visitado.
3. Procesar la cola
4. Desencolar u de la cola
5. Para todo adyacente a u,(u,v) Є E,
6. si v no ha sido visitado
7. encolar y visitar v
• Si desde u no fueran alcanzados todos los nodos del
grafo: volver a (1), elegir un nuevo vértice de
partida no visitado, y repetir el proceso hasta que
se hayan recorrido todos los vértices
Asignación semanal
• Investigar:
• Algoritmos para determinar el árbol de cobertura
mínimo en un grafo ponderado
• Algoritmos para encontrar el camino de menor costo
entre 2 nodos de un grafo.
