Lección 14: Grafos — BFS y DFS

Piensa en un mapa de ciudades conectadas por carreteras, o en amigos de una red social. Cualquier cosa que sea 'puntos y relaciones entre ellos' es un 'grafo': nodos conectados por aristas. Dos formas de recorrer un grafo: BFS se expande anillo por anillo como una onda en el agua, ideal para el cami

BFS es como una onda en el agua: empiezas en un punto y te expandes anillo por anillo hacia afuera, primero lo más cercano. DFS es como recorrer un laberinto: vas hasta el final por un camino, y si te atascas retrocedes e intentas otro.

recorrido de grafo: Visitar sistemáticamente cada nodo alcanzable desde un nodo inicial, usando BFS (una cola) o DFS (una pila/recursión).
diccionario de adyacencia: Una representación de grafo donde cada nodo se mapea a su lista de vecinos: {nodo: [vecinos]}: acceso a los vecinos en O(1).
conjunto de visitados: Un set que marca qué nodos ya fueron recorridos, para no visitarlos de nuevo y evitar bucles infinitos.