Scribd
Cargar
17 vistas13 páginas

Implementación de BFS y DFS en Grafos

La práctica 7 del curso de Estructura de Datos y Algoritmos 2 consiste en implementar los algoritmos BFS y DFS en un grafo que representa el metro de la CDMX para encontrar rutas entre estaciones. Se comparan las rutas generadas por ambos algoritmos, destacando que BFS encuentra la ruta más corta mientras que DFS explora todas las conexiones posibles. A pesar de las complicaciones en la implementación de DFS, el código funciona correctamente y permite modificar las estaciones iniciales y finales.

Cargado por

Miguel Angel Chávez Hernández
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
17 vistas13 páginas

Implementación de BFS y DFS en Grafos

La práctica 7 del curso de Estructura de Datos y Algoritmos 2 consiste en implementar los algoritmos BFS y DFS en un grafo que representa el metro de la CDMX para encontrar rutas entre estaciones. Se comparan las rutas generadas por ambos algoritmos, destacando que BFS encuentra la ruta más corta mientras que DFS explora todas las conexiones posibles. A pesar de las complicaciones en la implementación de DFS, el código funciona correctamente y permite modificar las estaciones iniciales y finales.

Cargado por

Miguel Angel Chávez Hernández
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

Carátula para entrega de prácticas

Facultad de Ingeniería Laboratorios de docencia

Laboratorio de Computación
Salas A y B
Profesor(a): Cruz Navarro Jesús

Asignatura: Estructura de Datos y Algoritmos 2

Grupo: 1

No de Práctica(s): Práctica 7

Integrante(s): Chávez Hernández Miguel Angel

No. de lista o No. Lista 3


brigada:

Semestre: 2025-1

Fecha de entrega: 29/09/24

Observaciones:

CALIFICACIÓN: ________________
Objetivos

1. Implementar los algoritmos BFS y DFS en la clase grafo.

2. Generar un programa que, utilizando el metro de la CDMX como un grafo,


encuentre la ruta entre dos estaciones mediante los algoritmos BFS y DFS.

3. Comparar las rutas generadas entre BFS y DFS.

Código Fuente
Datos de entrada y salida

(Grafo utilizado en la práctica anterior)


Análisis de resultados

El código fuente nos muestra una “lista de adyacencia” de dos tipos de rutas del
metro, el programador puede modificar la estación inicial y la estación final y
gracias a los algoritmos para recorrer grafos BFS y DFS podemos ver dos tipos de
caminos distintos, con BFS lo que logramos es obtener una de las rutas más
cortas que existen para llegar de un punto A a un punto B, en cambio con DFS
recorre todas las posibles conexiones entre ambos nodos, ambos se comportan
de una manera similar pero con sus respectivas diferencias, el código se comporta
de buena manera y como debería de ser a pesar de cambiar las estaciones
iniciales y finales.

Otros puntos

No se requirieron más puntos en la práctica.


Conclusiones

La verdad creo que esta práctica ha sido de las más tediosas en cuestión a trabajo
mecánico, en si ya habíamos realizado una parte del código con el profesor que
fue el algoritmo BFS y ya habíamos logrado que funcionara pero con un grafo más
pequeño, a la hora de implementar DFS si tuve un poco más de complicaciones ya
que el código de las presentaciones no era similar, de hecho, tuve que hacer
varias modificaciones en cuanto al código que ya habíamos realizado en el grafo
de la practica anterior, lo más talachudo que pude encontrar fue conectar cada
una de las estaciones y sus transbordos, aunque solo necesitábamos una sola
conexión ya que el grafo es no dirigido, el número de estaciones que maneja el
metro son muchísimas por lo cual si fue un poco difícil de manejar, en cuanto a
código pues ya teníamos la base entonces solo había que modificarlo conforme al
archivo del metro del profesor y a las conexiones entre cada una.

Por último solo queda responder ¿Cuál es el patrón que sigue DFS para generar
los caminos (a diferencia de BFS, que descubre la ruta más corta.)? Básicamente
BFS sigue la ruta más larga por así decirlo, ya que recorre los nodos más
alejados, en cambio BFS recorre la ruta más corta, algo que me di cuenta y me
causó curiosidad es que a pesar de que hayan 2 rutas distintas que tienen la
misma distancia siempre te imprime solo una, esto es raro pero a la vez supongo
que tendrá su explicación.

Referencias

Python: How exactly can you take a string, split it, reverse it and join it back together

again? (s. f.). Stack Overflow.

[Link]
string-split-it-reverse-it-and-join-it-

back#:~:text=The%20important%20parts%20here%20are%20the

Y las imágenes del metro y el archivo compartido por el profesor.

También podría gustarte