Grafos 02 - Recorridos

Al igual que para los árboles binarios, existen dos formas básicas de recorrer grafos: en profundidad (depth) y anchura (breadth).

Depth first search

La estrategia de DFS se puede resumir así:

dfs(v: Vertex)
----------------------
1.  Mark v as visited
2.  for (each unvisited vertex u adjacent to v)
3.    dfs(u)

Observaciones:

• El paso #2 no especifica el orden en que se visitaran los nodos adyacentes de un nodo u. En la práctica se usa el orden que menos esfuerzo requiera de la estructura que usamos para llevar cuenta de los nodos adyacentes.

• A diferencia del BFS para árboles, el BFS para grafos necesita un mecanismo para evitar visitar el mismo nodo más de una vez. De lo contrario el algoritmo podría nunca terminar.

• Para llevar cuenta de cuáles nodos han sido visitados comúnmente se utiliza un arreglo de booleanos tamaño $|V|$ donde $V$ es el conjunto de los nodos del grafo. El arreglo se inicializa a false al comienzo del recorrido.

• Cuando se implementa usando lista de adyacencias la complejidad de este algoritmo es $O(|V| + |E|)$ pues cada nodo es visitado una sola vez y cuando es visitado debe (en el peor de los casos) hacer un for para todas sus aristas.

• Cuando se implementa usando matriz de adyacencias la complejidad de $O(|V|^2)w$ pues para cada que visita debe revisar en $|V|$ entradas de la matriz.

Breadth first search

bfs(v: Vertex)
----------------------------------
1.  q is an empty queue
2.  // Add v to queue and mark it
3.  q.enqueue(v)
4.  Mark v as visited
5.  while (!q.isEmpty()) {
6.     q.dequeue(w)
7.     for (each unvisited vertex u adjacent to w) {
8.        Mark u as visited
9.        q.enqueue(u)
10.    }
11. } 

Observaciones:

• Al igual que en DFS podemos llevar cuenta de las visitas usando un arreglo de booleanos.

• La forma más natural de expresar este algoritmo es iterativa. Se puede hacer recursiva pero enloqueceras en el proceso :-).

• Cuando se implementa usando lista de adyacencias la complejidad de este algoritmo es O(|V| + |E|) pues cada nodo visitado es visitado una sola vez y cuando es visitado debe (en el peor de los casos) hacer un for para todas sus aristas (para determinar cuáles de sus vecinos no han sido visitados).

Ejercicios

1. En https://visualgo.net/en/dfsbfs, escoge algunas de los grafos de ejemplo y trata de predecir su orden de visita usando BFS y DFS. Luego simúlalos y corrobora tus contestaciones.

2. ¿Cómo compara el tiempo de ejecución de un grafo no-dirigido completo de 10 nodos vs otro grafo no-dirigido completo de 20 nodos?

3. ¿Cómo modificarías DFS para que solo recorra hasta nodos que queden a un máximo de distancia 2 del nodo inicial? Por ejemplo, para el siguiente grafo si comenzaramos el recorrido en el nodo 3 visitariamos a 2,4,6,7 y 5 pero no a 1.

   

4. ¿Cómo modificarías BFS para que solo recorra hasta nodos que queden a un máximo de distancia 2 del nodo inicial?