Inicio · Parte 04 — Matemática discreta para computación
coste BFS: O(V + E)
distancia BFS = número mínimo de aristas
excentricidad = máxima distancia desde un vérticeEl recorrido en anchura visita primero todos los vecinos, luego los vecinos de los vecinos, y así sucesivamente. Esa disciplina por niveles garantiza que la primera vez que se alcanza un vértice se ha hecho por el camino con menos aristas, que es el camino más corto en un grafo no ponderado.
La implementación necesita una cola (FIFO) y un conjunto de visitados. Cambiar la cola por una pila convierte el algoritmo en DFS, con propiedades muy distintas: DFS no garantiza caminos mínimos pero sirve para detectar ciclos y para ordenar topológicamente. La estructura de datos determina el comportamiento.
El coste O(V + E) es óptimo: cada vértice y cada arista se procesan una vez. Con pesos en las aristas, BFS deja de servir y hace falta Dijkstra, cuyo coste sube a O((V+E) log V) por la cola de prioridad.
La excentricidad de un vértice —la mayor distancia a cualquier otro— y el diámetro del grafo se calculan con BFS desde cada vértice. En redes sociales esas métricas dan lugar al fenómeno de los «seis grados de separación», y en un pipeline indican cuántas etapas secuenciales hay como mínimo.
BFS desde «entrada» en el pipeline.
orden de visita:
entrada → limpieza → features → split → entrenamiento → evaluacion
distancias (en aristas):
entrada 0
limpieza 1
features 2
split 2
entrenamiento 3
evaluacion 4
todos alcanzables: 6/6 ✓
excentricidad de entrada: 4
coste: O(V + E) = O(6 + 6)Recorrido BFS: alcanzabilidad y distancia en aristas.
python classes/part-04-matematica-discreta-para-computacion/094-caminos-ciclos-y-conectividad/lab.py
compmath run 094origenorden_de_visitadistanciastodos_alcanzablesexcentricidadcomplejidad_BFS{
"origen": "entrada",
"orden_de_visita": [
"entrada",
"limpieza",
"features",
"split",
"entrenamiento",
"evaluacion"
],
"distancias": {
"entrada": 0,
"limpieza": 1,
"features": 2,
"split": 2,
"entrenamiento": 3,
"evaluacion": 4
},
"todos_alcanzables": true,
"excentricidad": 4,
"complejidad_BFS": "O(V + E)"
}Camino más corto en grafos no ponderados, detección de componentes conexas, análisis de alcance en redes y niveles de un pipeline.
Los grafos de cómputo, la búsqueda en árbol y las GNN son estructuras discretas; el conteo sostiene la probabilidad que después usa todo modelo generativo.
9780262046305 verificado en International ISBN Agency (2026-08-19).collections.deque — documentación de la herramienta que ejecuta el laboratorio · URL de la fuente primaria comprobada en Python Software Foundation (2026-08-19).