Algoritmos de grafos

Vista previa del material en texto

Algoritmos Computacionales Grupo C 
M. Cruz Apuntes de prueba de regularización Curso de invierno 2022 
Algoritmos de grafos: búsqueda en profundidad (DFS) y 
búsqueda en amplitud (BFS) 
Los algoritmos de búsqueda en grafos son un tipo de 
algoritmo de recorrido que se utiliza para explorar todos 
los nodos de un grafo. 
Ideas principales para estudiantes de universidad 
Para los estudiantes de universidad, es importante 
comprender las siguientes ideas principales sobre los 
algoritmos de búsqueda en grafos: 
• Los algoritmos de búsqueda en grafos exploran 
todos los nodos de un grafo. 
• Los algoritmos de búsqueda en grafos se dividen 
en dos tipos principales: BFS y DFS. 
• BFS explora los nodos de un grafo en orden de 
distancia desde el nodo inicial. 
• DFS explora los nodos de un grafo en orden de 
profundidad, comenzando por el nodo inicial y 
luego explorando los nodos adyacentes a los 
nodos ya explorados. 
Recomendaciones para estudiantes de universidad 
Para los estudiantes de universidad que están 
aprendiendo sobre los algoritmos de búsqueda en 
grafos, se recomiendan las siguientes actividades: 
• Practicar mucho. La mejor manera de aprender 
sobre los algoritmos de búsqueda en grafos es 
practicar con frecuencia. 
• Buscar ayuda cuando sea necesario. Si tienes 
problemas para entender un concepto o resolver 
un problema, no dudes en pedir ayuda a un 
profesor o a un tutor. 
• Participar en proyectos. Trabajar en proyectos te 
ayudará a aplicar tus conocimientos sobre los 
algoritmos de búsqueda en grafos en el mundo 
real. 
Explicación 
Los algoritmos de 
búsqueda en grafos 
exploran todos los 
nodos de un grafo. Esto 
se hace siguiendo un 
conjunto de reglas que 
determinan qué nodos 
se exploran primero. 
Los algoritmos de 
búsqueda en grafos se 
dividen en dos tipos 
principales: BFS y DFS. 
BFS 
BFS explora los nodos 
de un grafo en orden de 
distancia desde el nodo 
inicial. El algoritmo 
comienza por el nodo 
inicial y luego explora 
todos los nodos 
adyacentes a este nodo. 
Luego, el algoritmo 
explora todos los nodos 
adyacentes a los nodos 
ya explorados, y así 
sucesivamente. 
BFS es un algoritmo 
eficiente para encontrar 
el camino más corto 
entre dos nodos de un 
grafo. 
DFS 
DFS explora los nodos 
de un grafo en orden de 
profundidad, 
comenzando por el 
nodo inicial y luego 
explorando los nodos 
adyacentes a los nodos 
ya explorados. 
Algoritmos Computacionales Grupo C 
M. Cruz Apuntes de prueba de regularización Curso de invierno 2022 
DFS es un algoritmo eficiente para encontrar todos los 
caminos entre dos nodos de un grafo. 
Ejemplos de algoritmos de búsqueda en grafos 
Algunos ejemplos de algoritmos de búsqueda en grafos 
incluyen: 
• El problema del camino más corto: Este 
problema consiste en encontrar el camino más 
corto entre dos nodos en un grafo. Un algoritmo 
de BFS o DFS se puede utilizar para resolver 
este problema. 
• El problema del árbol de expansión mínima: Este 
problema consiste en encontrar un árbol que 
conecte todos los nodos de un grafo de tal 
manera que la suma de las longitudes de las 
aristas del árbol sea mínima. Un algoritmo de 
BFS se puede utilizar para resolver este 
problema. 
• El problema de la búsqueda de caminos: Este 
problema consiste en encontrar todos los 
caminos entre dos nodos en un grafo. Un 
algoritmo de DFS se puede utilizar para resolver 
este problema. 
Ventajas y desventajas de los algoritmos de búsqueda 
en grafos 
Ventajas: 
• Los algoritmos de búsqueda en grafos pueden 
encontrar todos los caminos entre dos nodos de 
un grafo. 
• Los algoritmos de búsqueda en grafos pueden 
encontrar el camino más corto entre dos nodos 
de un grafo. 
Desventajas: 
• Los algoritmos de búsqueda en grafos pueden 
ser complejos de implementar. 
• Los algoritmos de búsqueda en grafos pueden 
requerir una gran cantidad de memoria. 
Conclusión 
Los algoritmos de 
búsqueda en grafos son 
una herramienta 
poderosa para explorar 
todos los nodos de un 
grafo. BFS y DFS son 
dos algoritmos de 
búsqueda en grafos 
comunes que se utilizan 
para diferentes 
propósitos.