Recorrer
un grafo significa tratar de alcanzar todos los nodos que estén relacionados
con uno que llamaremos nodo de salida. Existen básicamente dos técnicas para
recorrer un grafo: el recorrido en anchura y el recorrido en profundidad.
Así,
para recorrer un grafo consiste en visitar todos los vértices alcanzables a partir
de uno dado. Hay dos formas.
·
Recorrido en profundidad
Recorrido en
Profundidad (DFS):
Trata de buscar los
caminos que parten desde el nodo de salida hasta que ya no es posible avanzar
más. Cuando ya no puede avanzarse más sobre el camino elegido, se vuelve atrás
en busca de caminos alternativos, que no se estudiaron previamente.
Recorrido en Anchura
(BFS):
Supone recorrer el
grafo, a partir de un nodo dado, en niveles, es decir, primero los que están a
una distancia de un arco del nodo de salida, después los que están a dos arcos
de distancia, y así sucesivamente hasta alcanzar todos los nodos a los que se
pudiese llegar desde el nodo salida.
No hay comentarios:
Publicar un comentario