4.3.1. Recorridos sobre grafos.
Ejemplo: Prueba de aciclicidad. Dado un grafo (dirigido o no dirigido) comprobar si tiene ciclos o no.
- Grafo no dirigido. Realizar una búsqueda primero en profundidad. Si aparece algún arco que no es del árbol entonces existe un ciclo.
- Grafo dirigido. Realizar una búsqueda primero en profundidad. Si aparece algún arco de retroceso entonces existe un ciclo.
Orden de complejidad del recorrido en profundidad.
- Con listas de adyacencia, se recorre cada elemento de lista una vez, O(a+n).
- Con matrices de adyacencia, para cada nodo se buscan sus adyacentes, O(n2).
Búsqueda primero en profundidad
Grafo dirigido Bosque abarcador en profundidad