ESCUELA MILITAR DE INGENIERIA
“MCAL ANTONIO JOSE DE SUCRE”
RECORRIDO DE GRAFOS
ESTUDIANTES:
- ALARCON TAQUICHIRI ANGELA ABRIL
- APAZA GUTIERREZ JUAN CARLOS
- CAYLLANTE SIRPA FERNANDO
- LOPEZ MAMANI YUSETH NATALY
CARRERA: INGENIERIA DE SISTEMAS
ASIGNATURA:PROGRAMACION AVANZADA
FECHA:27-04-21
DOCENTE: MAGUEÑO GORDILLO GROVER
MILTON
GESTION 2021
RECORRIDO DE GRAFOS (GRAPH TRAVERSAL)
En informática, el recorrido de grafos (también conocido como búsqueda de
grafos) se refiere al proceso de visitar (verificar y / o actualizar) cada vértice de un
grafo.
Dichos recorridos se clasifican por el orden en que se visitan los vértices.
Se conocen lo siguientes algoritmos de recorrido:
Algoritmo de Búsqueda BFS y DFS.
Algoritmos Pesados: Algoritmo Dijkstra.
Mínimos de Arboles: Algoritmo de Prim, Algoritmo de Kruskal
Rutas cortas: Algoritmo Random Walk,Algoritmo A*, algoritmo de rutas K de
Yen
ALGORITMO DE BFS
Descripción
Este algoritmo de grafos es muy útil en diversos problemas de programación. Por
ejemplo halla la ruta más corta cuando el peso entre todos los nodos es 1, cuando
se requiere llegar con un movimiento de caballo de un punto a otro con el menor
número de pasos, cuando se desea transformar algo un numero o cadena en otro
realizando ciertas operaciones como suma producto, pero teniendo en cuenta que
no sea muy grande el proceso de conversión, o para salir de un laberinto con el
menor número de pasos , etc. Podrán aprender a identificarlos con la práctica.
Como trabaja
BFS va formando un árbol a medida que va recorriendo un grafo, veamos el
ejemplo de la figura:
Si observan bien todo parte de un nodo inicial que será la raíz del árbol que se
forma, luego ve los adyacentes a ese nodo y los agrega en una cola, como la
prioridad de una cola es FIFO (primero en entrar es el primero en salir), los
siguientes nodos a evaluar serán los adyacentes previamente insertados. una
cosa bastante importante es el hecho de que no se pueden visitar 2 veces el
mismo nodo o Estado. ya que sino podríamos terminar en un ciclo interminable o
simplemente no hallar el punto deseado en el menor número de pasos.
ALGORITMO EN PSEUDOCODIGO
1 método BFS(Grafo,origen):
2 creamos una cola Q
3 agregamos origen a la cola Q
4 marcamos origen como visitado
5 mientras Q no este vacío:
6 sacamos un elemento de la cola Q llamado v
7 para cada vertice w adyacente a v en el Grafo:
8 si w no ah sido visitado:
9 marcamos como visitado w
10 insertamos w dentro de la cola Q
ALGORITMO DE DFS
Descripción
El algoritmo DFS posee varias aplicaciones la más importante es para problemas
de conectividad, si un grafo es conexo, detectar ciclos en un grafo, numero de
componentes conexas, etc y es bastante útil en otro algoritmos como para hallar
las componentes fuertemente conexas en un grafo ( Algoritmo de Kosaraju,
Algoritmo de Tarjan), para hallar puntos de articulación o componentes biconexas
( puentes ), para recorrido en un circuito o camino euleriano, topological sort, flood
fill y otras aplicaciones.
DFS va formando un árbol al igual que BFS pero lo hace a profundidad. Existen
dos formas de hacer el recorrido una es usando una Pila y otra de manera
recursiva
Usando Stack
El concepto es el mismo que BFS solo que se cambia la Cola por una Pila, el
proceso es como sigue: visitar el nodo inicial y ponerlo en la pila, ahora para ver
los siguientes nodos a visitar sacamos el nodo tope de la pila y vemos sus
adyacentes, los que no han sido visitados los insertamos en la pila. El proceso se
repite hasta que la pila se encuentre vacía (se han visitado todos los nodos).
ALGORITMO EN PSEUDOCODIGO
1 método DFS( origen):
2 creamos una pila S
3 agregamos origen a la pila S
4 marcamos origen como visitado
5 mientras S no este vacío:
6 sacamos un elemento de la pila S llamado v
7 para cada vertice w adyacente a v en el Grafo:
8 si w no ha sido visitado:
9 marcamos como visitado w
10 insertamos w dentro de la pila S
Usando Recursión
Usar la recursión es mucho más fácil y además muy útil, es la forma más usada en
la solución de problemas con este algoritmo.
ALGORITMO EN PSEUDOCODIGO
1 método DFS( origen):
2 marcamos origen como visitado
3 para cada vertice v adyacente a origen en el Grafo:
4 si v no ha sido visitado:
5 marcamos como visitado v
6 llamamos recursivamente DFS( v )
ALGORITMO DE DIJKSTRA
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es
un algoritmo para la determinación del camino más corto dado un vértice origen al
resto de los vértices en un grafo con pesos en cada arista. Su nombre se refiere
a Edsger Dijkstra, quien lo describió por primera vez en 1959.
El algoritmo es una especialización de la búsqueda de costo uniforme y como tal ,
no funciona en grafo con aristas de costo negativo (al elegir siempre el nodo con
distancia menor pueden quedar excluidos de la búsqueda nodos que en próximas
iteraciones bajarían el costo general del camino al pasar por una arista con costo
negativo).
Características del algoritmo
• Trabaja por etapas y toman en cada etapa la mejor solución sin considerar
consecuencias futuras.
• El óptimo encontrado en una etapa puede modificarse posteriormente si
surge una solución mejor.
Como trabaja:
Primero marcamos todos los vértices como no utilizados. El algoritmo parte de un
vértice origen que será ingresado, a partir de esos vértices evaluaremos sus
adyacentes, como dijkstra usa una técnica greedy-La técnica greedy utiliza el
principio de que para que un camino sea óptimo, todos los caminos que contiene
también deben ser óptimos-entre todos los vértices adyacentes, buscamos el que
este más cerca de nuestro punto origen, lo tomamos como punto intermedio y
vemos si podemos llegar más rápido a través de este vértice a los demás.
Después escogemos al siguiente más cercano (con las distancias ya actualizadas)
y repetimos el proceso. Esto lo hacemos hasta que el vértice no utilizado más
cercano se nuestro destino. Al proceso de actualizar las distancias tomando como
punto intermedio al nuevo vértice se le conoce como relajación (relaxation).
ALGORITMO DE PRIM
Diseñado por primera vez en 1930 por el matemático Vojtech Jarnik y luego de
manera independiente por el científico Robert C. Prim en 1957 y redescubierto por
Dijkstra en 1959. Debido a esto a este algoritmo se lo conoce también como
algoritmo DJP o algoritmo de Jarnik. El algoritmo de Prim encuentra un árbol de
expansión de un grafo, cuyas aristas sumadas nos den el peso mínimo.
Algoritmo de Prim Ejecución de algoritmo
• Se marca un vértice cualquiera como vértice de partida.
• Seleccionamos una arista de menor valor del vértice marcado previamente y
marcamos el otro nodo con el que se conecta la arista.
• Repetimos el paso anterior siempre que la arista elegida enlace un nodo
marcado con otro que no lo esté.
• El proceso termina cuando tenemos todos los vértices del grafo marcados.
Ejemplo:
ALGORITMO DE KRUSKAL
Fue escrito por Joshep Kruskal y publicado en 1956 cuando trabajaba de
investigador en Math Center. El objetivo del algoritmo de kruskal es construir un
árbol formado por aristas sucesivamente seleccionadas de mínimo peso a partir
de un grafo con pesos en las aristas.
Algoritmo de Kruskal Ejecución del algoritmo
• Seleccionar la arista de menor costo.
• Si la arista seleccionada conecta dos vértices distintos, entonces marcamos la
arista verificando que no se formen ciclos.
• Continuamos el proceso hasta marcar todos los vértices.
Ejemplo:
RUTAS CORTAS. -
Los algoritmos de detección de rutas cortas son una importante rama de apoyo al
estudio de datos complejos contenidos en grafos. Gracias a ellos podemos
determinar caminos o recorridos dentro de la estructura de un grafo de forma
eficiente y rápida.
El algoritmo de rutas más cortas es en uno de los módulos de análisis más
importantes de los algoritmos de grafos Este se encarga de detectar dentro de un
grafo cuál es la ruta más eficiente o el recorrido de menor distancia entre un par de
vértices que conforman un grafo. Dentro de esta categoría destaca el conocido
algoritmo de Dijkstra por sus propiedades. A continuación, conoceremos aspectos
fundamentales para entender el funcionamiento de este algoritmo, conoceremos un
ejemplo de aplicación para profundizar más al respecto.
Algoritmo de rutas más corta o Dijkstra. -
El conocido algoritmo Dijkstra o algoritmo de ruta más corta es uno de los más
eficientes de esta familia. Nace basado en la teoría de Dijkstra que buscaba darle
solución al legendario planteamiento de la teoría de grafos: conseguir rutas más
cortas para diferentes casos. Con este planteamiento se logra dar una solución
especial al dilema de los caminos cortos con un rango de comprensibilidad para
personas que no pertenecen en su totalidad al mundo de la informática.
Este algoritmo estudia todas y cada una de las conexiones que presenta un vértice
dado y a partir de eso se determina la ruta más corta y eficiente para realizar el
recorrido por el grafo. Este algoritmo se orienta principalmente a estudiar estructuras
de grafos se ejecuta en tiempo real y puede ser utilizado en diferentes casos.
Algoritmo de rutas K de Yen. -
El algoritmo de rutas más cortas K del Yen es el que se encarga de estudiar los
grafos para determinar rutas o recorridos que no posean bucles de tipo K. Esto nos
permite encontrar rutas más cortas desde una fuente o vértice único desde un grafo
que posea pesos de relación no negativos.
Este algoritmo fue definido por Jin Y Yen en el año 1971 en un trabajo académico
titulado «Encontrando el camino más corto K sin bucles en una red.
Para poder encontrar una ruta eficiente utilizando este algoritmo en primer lugar
debe utilizarse una ejecución del algoritmo de Dijkstra y posteriormente encontrar
con este algoritmo las desviaciones producto de K-1 en las rutas.
Funcionamiento. -
1. Hallar el camino de menor coste para determinar A1, es decir, la primera
iteración del algoritmo con el camino de coste mínimo, a través de un
algoritmo de búsqueda del camino más corto.
2. Modificar el camino previo y eliminar el enlace de menor coste para generar
una ruta diferente entre el nodo fuente S y el nodo destino D. Almacenar el
nuevo trayecto generado en un array temporal B.
3. Repetir el paso 2 para cada enlace del camino más breve hallado
anteriormente.
4. Ordenar todos los caminos almacenados en orden ascendente y guardarlos
en el array A. Repetir para K-1 veces.
Ejemplo:
El mismo algoritmo asume que para encontrar el primer camino de menor coste se
use un algoritmo para ello, como puede ser el algoritmo de Dijkstra o el BFS. En las
iteraciones sucesivas se procederá a realizar algunas modificaciones al camino
previo para generar las rutas alternativas y ordenarlas por orden de coste. El
algoritmo devolverá un array Ak con los K caminos explorados y en orden creciente,
es decir, ordenado por el resultado de coste mínimo de cada trayecto analizado.
Algoritmo A*
El algoritmo conocido como A* es una optimización de los postulados del algoritmo
Dijsktra para descubrir rutas más cortas dentro de un grafo. En esta modificación se
toma como punto de inicio a la observación del grafo las búsquedas informadas que
existen para tomar decisiones óptimas sobre los caminos a seguir. Su teoría tiene
nacimiento en el año 1968 y fue desarrollado principalmente para aportar elementos
a la determinación de rutas de costo mínimo.
Funcionamiento. -
A* es un algoritmo informado que basa su comportamiento en la evaluación de una
función expresada del siguiente modo:
f(n) = g(n) + h(n)
La función se encuentra compuesta por:
✓ g(n) : es el costo de las movidas realizadas.
✓ h(n) : es la función heurística. Representa el costo estimado del mejor
camino.
Dicha estimación debe ser realizada por defecto, es decir, siempre menor o igual a
la real. En búsqueda de caminos, la función heurística suele ser el camino recto
hacia la meta, ya que no importa como sea el mapa, es imposible que exista camino
de costo menor.
El modo de realizar el cálculo de la distancia necesaria para llegar a la meta
depende del tipo de movidas permitidas. Si solo podemos movernos vertical y
horizontalmente podremos realizar el cálculo de la distancia Manhattan, que
consiste en sumar la cantidad de bloques en horizontal y vertical que restan para
llegar a la meta. Si además se permiten movidas diagonales, deberemos aplicar
Pitágoras y el cálculo será la raíz cuadrada de la suma de los cuadrados de los
catetos.
Ejemplo:
S representa el punto de partida. La bandera azul representa la meta. Los casilleros
de color negro representan obstáculos y los casilleros blancos representan caminos
posibles.
Nuestra función heurística será:
Una vez abiertas las bases del nivel, deberemos elegir cual tomar para seguir
nuestro camino. Para esto, siempre deberemos seleccionar la de menor f (en caso
de haber más de una con mismo valor, la elección es arbitraria). Siguiendo nuestro
ejemplo, deberemos seleccionar la movida 2.
Evaluamos las movidas posibles a partir de la posición elegida y volvemos a
seleccionar la de menor f. Es muy importante destacar que en dicha elección
también intervienen las bases abiertas en las movidas anteriores (que en el árbol
están pintadas de color amarillo). Por lo tanto, es posible (y muy factible) que en un
determinado momento el algoritmo abandone el camino por el cual se dirige para
"probar suerte" por otro lado.
Aplicando varias movidas las novedades son las siguientes: Abandonamos el
camino por la movida 4 debido a que quedamos encerrados. Intentamos seguir por
el camino de la movida 1 pero tampoco nos llevaba a ningún lado. Tomamos el
camino de la movida 3 y avanzamos por el único lugar que podemos.
Continuamos avanzando por el mapa, hemos abierto las bases 6 y 7, de las cuales
seleccionamos la 6. A partir de allí abrimos las bases 8, 9 y 10, de las cuales como
se puede apreciar en el árbol de la figura anterior, seleccionaremos la 8
Algoritmo Random Walk.-
El conocido algoritmo Random Walk o de camina aleatoria es creado con la función
de determinar rutas cortas dentro de la estructura de un grafo recorriendo nodos
vecinos escogidos de forma aleatoria o en función de una distribución de
probabilidad proporcionada. Una vez se completa el recorrido, el nodo o vértice de
llegada se convierte en un nuevo punto de salida para determinar más rutas.
Un Random Walk es, como su nombre indica, un camino aleatorio sobre un grafo.
Comienza desde un vértice (que puede ser uno específico o uno aleatorio) y se
mueve aleatoriamente a un vecino; y luego, se mueve a un vecino (incluyendo el
original) desde el nuevo vértice.
Este proceso continúa hasta que el recorrido tenga un largo n prefijado. La
probabilidad para movernos de un vértice a un vecino puede ser equiprobable (la
misma para todos) o proporcional al peso que tenga cada arista (si el grafo fuera
pesado), u otra alternativa dependiendo de la aplicación. Finalmente, una aplicación
que utiliza este algoritmo puede realizar varios recorridos. Por lo tanto, para realizar
un random walk es necesario determinar:
✓ El largo del recorrido.
✓ La probabilidad para movernos desde un vértice a sus vecinos.
✓ La cantidad de recorridos a realizar.
Todas estas caracterizaciones dependen de la aplicación del algoritmo
