4.3. Problemas y algoritmos sobre grafos.
Igual que los recorridos en árboles, se parte de un nodo dado y sirven para visitar los vértices y los arcos de manera sistemática.
Existen dos tipos de recorridos:
- Búsqueda primero en profundidad. Es equivalente a un recorrido en preorden de un árbol. Se elige un nodo v de partida. Se marca como visitado y se recorren los nodos no visitados adyacentes a v, usando recursivamente la búsqueda primero en profundidad.
- Búsqueda primero en amplitud o anchura. Es equivalente a recorrer un árbol por niveles. Dado un nodo v, se visitan primero todos los nodos adyacentes a v, luego todos los que están a distancia 2 (y no visitados), a distancia 3, y así sucesivamente hasta recorrer todos los nodos.
El recorrido puede ser para grafos dirigidos o no dirigidos.
En los dos casos es necesario llevar una cuenta de los nodos visitados.
4.3.1. Recorridos sobre grafos.
marca: array [1..num_nodos] of
for v:= 1 to num_nodos do