Recorridos de grafos

Un Recorrido en profundidad (en inglés DFS o Depth First Search) es un algoritmo que permite recorrer todos los nodos de un grafo. Es una generalización del recorrido preorden de un árbol.

La estrategia consiste en partir de un vértice determinado v y a partir de alli, cuando se visita un nuevo vértice, explorar cada camino que salga de él. Hasta que no se haya finalizado de explorar uno de los caminos no se comienza con el siguiente. Un camino deja de explorarse cuando se llega a un vértice ya visitado.

Si existían vértices no alcanzables desde v el recorrido queda incompleto; entonces, se debe seleccionar algún vértice como nuevo vértice de partida, y repetir el proceso.

Pérez, G. M. C.-. (2022). DFS - Recorrido en profundidad | Recorridos sobre grafos. DFS - Recorrido en profundidad. https://163.10.22.82/OAS/recorrido_grafos/dfs__recorrido_en_profundidad.html

Presentación para los recorridos en los grafos:

Plantilla para practicar los recorridos en los grafos:

Actividad en clase:

Nota: Realizar el ejercicio propuesto al final de las Diapositivas..

Contesta las siguientes preguntas dando una explicación corta:

1. Qué relación hay entre la estructura árbol y la estructura grafo? Puede ser un grafo un árbol?
2. Es un grafo una estructura recursiva? Explique
3. Para qué tipo de problemas se utiliza la estructura grafo? De dos ejemplos
4. Como se puede representar la estructura grafo? Explique
5. Construya dos grafos: Uno dirigido y otro no dirigido

Desarrollo

1. Un árbol es un grafo simple no dirigido, es un grafo en el que cualquier par de vértices están conectados por exactamente un camino.

2. Si es una estructura recursiva porque en su recorrido como lo miramos anteriormente se puede volver a llamar las veces que sean necesarias o según se lo requiera.

3. Son muchos los problemas que se pueden solucionar con un grafo ya que hay muchos tipos de grafos y estos se ajustan cada uno a cierta situación entonces dos ejemplos claros serían: El transporte y las redes sociales. En el transporte los grafos son perceptibles en las carreteras y mapas, pero en las redes sociales están implícitos de manera que aunque no los observemos, cumplen una gran función. 

4. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas). Y a la vez estos según la cantidad de aristas o vértices pueden ser clasificados en ciertos grupos. 

5. Grafo dirigido: 

Grafo no dirigido: