Recorrido de grafos

¿Para qué se necesita recorrer un grafo?

• Encontrar todos los vértices alcanzables desde un vértice dado
• Encontrar el mejor camino de un vértice a otro
• Averiguar si un grafo tiene o no ciclos
• Realizar un procesamiento sobre cada nodo que cumpla determinada condición

DFS: Búsqueda en profundidad

Es un algoritmo que nos permite recorrer los nodos de un grafo de manera ordenada pero no uniforme.

Su funcionamiento consiste en recorrer un camino concreto hasta donde se pueda, si quedan nodos sin recorrer retrocede sobre si mismo y recorre otro camino

<aside> 💡 Para su implementación en código se utiliza un array para marcar los nodos visitados y una pila para guardar el camino actual

</aside>

En resumen, la búsqueda en profundidad nos permite:

• Recorrer los nodos accesibles desde un nodo inicial (en grafos dirigidos y no dirigidos)
• Detectar ciclos
• Detectar subgrafos (grafos no dirigidos)
• Detectar componentes conexas (grafos dirigidos)
• Encontrar árboles de recorrido

BFS: Búsqueda primero en anchura

Es un algoritmo que además de recorrer un grafo, puede calcular las distancias de un nodo de un grafo a todos los demás

Funciona empezando desde un nodo desde el cual queremos calcular la distancia a todos los demás y se mueve a todos sus vecinos, una vez que hizo esto, se mueve a los vecinos de sus vecinos, y así hasta recorrer todos los nodos del grafo.