Algoritmos de Recorrido en Grafos: Profundidad y Anchura

Recorrido de un grafo

Recorrido en profundidad (DFS)

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 el recorrido en profundidad.

1. Meter vértice de partida en visitados.
2. Apilar vértice de partida.
3. Repetir los pasos 4 a 6 hasta que la pila esté vacía.
4. Imprimir w = cima(P) y desapilar.
5. Apilar los nodos adyacentes de w no visitados.
6. Meter los nodos adyacentes de w en visitados.

Recorrido en anchura (BFS)

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.

1. Meter vértice de partida en visitados.
2. Encolar vértice de partida.
3. Repetir los pasos 4 a 6 hasta que la cola esté vacía.
4. Imprimir w = primero(C) y desencolar.
5. Encolar los nodos adyacentes de w no visitados.
6. Meter los nodos adyacentes de w en visitados.

Grafo conexo

El grafo es conexo si el conjunto de vértices visitados coincide con todos los vértices del grafo. Si un grafo no es conexo, pueden encontrarse subgrafos que sí lo sean; a estos se les llama componentes fuertemente conexas.

Grafo fuertemente conexo

• Obtener el conjunto de descendientes de un vértice de partida v, D(v), incluido el propio vértice.
• D(v) se calcula haciendo un recorrido en anchura o profundidad desde el propio vértice.
• Obtener el conjunto de ascendientes de un vértice de partida v, A(v), incluido el propio vértice.
• A(v) se calcula cambiando el sentido de todos los arcos del grafo y haciendo un recorrido en anchura o profundidad desde el propio vértice.
• Las componentes fuertemente conexas (CFC) que contienen al vértice v son D(v) ∩ A(v).
• Si este conjunto es igual al conjunto de vértices del grafo, entonces el grafo es conexo.
• Si no, seleccionar un vértice cualquiera w que no esté en ninguna CFC y repetir el proceso.