4.3.1. Recorridos sobre grafos.
Búsqueda primero en profundidad
¿Cómo comprobar si un arco es de avance, retroceso o cruce?
Solución: Al hacer el recorrido construir explícitamente el árbol de expansión, usando una estructura de punteros al padre.
marca: array [1..num_nodos] of integer;
- marca[v] valdrá: -1 si v no está visitado; 0 si está visitado y es raíz de un árbol; en otro caso indicará cual es el padre de v.
- Modificar los procedimientos BorraMarcas, BuscaPrimeroProfundidad y bpp, para construir el árbol.
- Arco de avance <v, w>: w es hijo de v en uno de los árboles del bosque.
- Arco de retroceso <v, w>: v es hijo de w.
- Arco de cruce <v, w>: si no se cumple ninguna de las anteriores.
Búsqueda primero en amplitud o anchura
Se comienza por un vértice elegido v. Se visitan todos sus adyacentes. Luego los adyacentes de estos y así sucesivamente.
Para ello se utiliza una cola de vértices. Operaciones básicas:
- Sacar un elemento de la cola.
- Añadir sus adyacentes a la cola (si no están visitados).