Algoritmo de Búsqueda en Anchura (BFS)
Imagina que, dado un grafo con
n vértices y e aristas, quieres comenzar desde un vértice y recorrer gradualmente todo el grafo visitando todos los vértices que sean alcanzables desde el punto de partida. Hay varias maneras de hacerlo, pero uno de los métodos más conocidos es el algoritmo BFS (Búsqueda en Anchura). Por su naturaleza, BFS permite calcular la ruta más corta desde un vértice inicial hasta todos los demás vértices del grafo, lo que lo hace muy útil en diversas aplicaciones.
Una forma muy práctica de conceptualizar el algoritmo BFS es pensar en “incendiar” el grafo y observar cómo se propaga el fuego. Imagina que cada vértice tarda 1 minuto en quemarse; después de ese minuto, el fuego se extiende a sus vecinos inmediatos, quienes a su vez se queman en el transcurso de 1 minuto, y el fuego pasa a sus vecinos, y así sucesivamente.
Entonces, enciendes el vértice inicial. Luego el fuego se propaga a todos sus vecinos. Tras esperar un minuto, comienza a quemarse el vecindario de esos vecinos, y después les toca a los vecinos de esos vecinos. Este proceso continúa hasta que ya no quedan vértices sin quemar. Tener esta imagen mental de cómo el fuego quema el grafo por completo ayuda mucho a la hora de implementar el algoritmo BFS.
La implementación del algoritmo BFS puede hacerse usando una
queue y una lista de vértices que lleve el registro de aquellos vértices used (en llamas, o visitados):from collections import deque
n, e = map(int, input().split()) # n: vértices, e: aristas
g = [[] for _ in range(n)] # grafo - lista de adyacencia
for _ in range(e): # leer aristas
a, b = map(int, input().split()) # a -> b y b -> a
g[a].append(b)
g[b].append(a)
start = int(input()) # vértice inicial
used = [False] * n # vértices utilizados (visitados)
q = deque([start]) # cola de vértices
used[start] = True # marcar el vértice inicial como visitado
while q: # mientras la cola no esté vacía
v = q.popleft() # sacar vértice de la cola
print(v, end=' ') # imprimir vértice
for to in g[v]: # para cada vértice conectado a v
if not used[to]: # si el vértice no ha sido visitado
q.append(to) # agregar vértice a la cola
used[to] = True # marcar vértice como visitadoAquí, primero inicializamos el grafo y comenzamos el recorrido desde el vértice
start. Al inicio, todos los valores de used están establecidos como False. Después de visitar cada vértice, lo agregamos a la cola y lo marcamos como usado. Esto simula la “quema” del grafo. En cada paso, añadimos a la cola todos los vértices adyacentes que no estén marcados como usados y luego los marcamos para indicar que ya han “ardido”.Veamos algunos ejemplos de cómo funciona el algoritmo con distintas entradas:
n = 4, e = 4
Las parejas de entrada
a, b son: [(0, 1), (0, 2), (1, 2), (3, 2)]El vértice inicial es 3
used = [False, False, False, True],q = [3]
v = 3,q = []→ añadir todos los vecinos no usados a la cola
used = [False, False, True, True],q = [2]
v = 2,q = []→ añadir todos los vecinos no usados a la cola
used = [True, True, True, True],q = [0, 1]
v = 0,q = [1]→ añadir todos los vecinos no usados a la cola
v = 1,q = []→ añadir todos los vecinos no usados a la cola
- Terminado
n = 5, e = 4
Las parejas de entrada
a, b son: [(0, 1), (0, 2), (1, 2), (3, 4)]El vértice inicial es 0
used = [True, False, False, False, False],q = [0]
v = 0,q = []→ añadir todos los vecinos no usados a la cola
used = [True, True, True, False, False],q = [1, 2]
v = 1,q = [2]→ añadir todos los vecinos no usados a la cola
v = 2,q = []→ añadir todos los vecinos no usados a la cola
- Terminado
Notice how nodes 3 and 4 were never visited.
They were not connected to the initial node 0.
Desafío: Contar el Número de Componentes Conexas en un Grafo
Dado un grafo no dirigido con
v vértices y e aristas, se te pide calcular el número de componentes conexas del grafo. Un conjunto de vértices se considera una componente conexa si es posible viajar entre todos ellos.Entrada
La primera línea de la entrada contiene dos enteros
v (1 ≤ v ≤ 100 000) y e (1 ≤ e ≤ 100 000).Las siguientes
e líneas contienen parejas de enteros v1, v2 (1 ≤ v1, v2 ≤ v) que indican que el vértice v1 está conectado con el vértice v2 y viceversa.Salida
El programa debe imprimir el número de componentes conexas en el grafo.
Ejemplos
Entrada | Salida |
7 6
1 2
2 3
1 3
4 5
5 6
4 6 | 3 |
2 1
1 2 | 1 |
2 0 | 2 |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB