Algoritmo di Breadth First Search (BFS)
Immagina di avere un grafo con
n vertici e e archi: vuoi partire da un vertice e, a poco a poco, esplorare tutto il grafo visitando tutti i vertici raggiungibili dal punto di partenza. Esistono diversi metodi per farlo, e uno dei più noti è l’algoritmo di Breadth-First-Search (BFS). Grazie alle sue caratteristiche, il BFS consente di calcolare il cammino più corto dal vertice sorgente a tutti gli altri vertici del grafo, rendendolo estremamente utile in molte applicazioni.
Un buon modo per immaginare l’algoritmo BFS è pensare a un fuoco che “brucia” il grafo e si propaga gradualmente. Ogni vertice brucia per 1 minuto, dopodiché il fuoco si estende ai suoi vicini, che bruciano a loro volta per 1 minuto, e così via.
In pratica, si “incendia” il vertice iniziale. Poi il fuoco si propaga a tutti i suoi vicini. Dopo un minuto, i vicini dei vicini iniziano a bruciare, e da lì il fuoco si estende ai loro vicini, continuando finché non rimangono più vertici da bruciare. Tenere a mente quest’immagine di un incendio che si diffonde è molto d’aiuto per implementare il BFS.
L’implementazione del BFS può essere realizzata usando una
queue (coda) e mantenendo un elenco di vertici used (visitati), che simula i vertici già “bruciati”:from collections import deque
n, e = map(int, input().split()) # n: vertici, e: archi
g = [[] for _ in range(n)] # grafo - lista di adiacenza
for _ in range(e): # leggi gli archi
a, b = map(int, input().split()) # a -> b e b -> a
g[a].append(b)
g[b].append(a)
start = int(input()) # vertice di partenza
used = [False] * n # vertici già visitati
q = deque([start]) # coda di vertici
used[start] = True # segna il vertice di partenza come visitato
while q: # finché la coda non è vuota
v = q.popleft() # estrai un vertice dalla coda
print(v, end=' ') # stampa il vertice
for to in g[v]: # per ogni vertice collegato a v
if not used[to]: # se non è ancora visitato
q.append(to) # aggiungi il vertice in coda
used[to] = True # segna il vertice come visitatoPer prima cosa inizializziamo il grafo e partiamo dal vertice
start. All’inizio, tutti i valori di used sono False. Quando visitiamo un vertice, lo inseriamo nella coda e lo contrassegniamo come usato. Questo simula il “bruciare” del grafo. A ogni passaggio, aggiungiamo alla coda tutti i vertici adiacenti non ancora usati del vertice corrente v e li marchiamo come usati.Vediamo come funziona l’algoritmo con alcuni esempi:
n = 4, e = 4
Le coppie
a, b in ingresso sono: [(0, 1), (0, 2), (1, 2), (3, 2)]Il vertice di partenza è 3
used = [False, False, False, True],q = [3]
v = 3,q = []→ aggiungi tutti i vicini non usati in coda
used = [False, False, True, True],q = [2]
v = 2,q = []→ aggiungi tutti i vicini non usati in coda
used = [True, True, True, True],q = [0, 1]
v = 0,q = [1]→ aggiungi tutti i vicini non usati in coda
v = 1,q = []→ aggiungi tutti i vicini non usati in coda
- Fine
n = 5, e = 4
Le coppie
a, b in ingresso sono: [(0, 1), (0, 2), (1, 2), (3, 4)]Il vertice di partenza è 0
used = [True, False, False, False, False],q = [0]
v = 0,q = []→ aggiungi tutti i vicini non usati in coda
used = [True, True, True, False, False],q = [1, 2]
v = 1,q = [2]→ aggiungi tutti i vicini non usati in coda
v = 2,q = []→ aggiungi tutti i vicini non usati in coda
- Fine
Notice how nodes 3 and 4 were never visited.
They were not connected to the initial node 0.
Sfida: Calcolare il numero di componenti connesse di un grafo
Dato un grafo non orientato con
v vertici e e archi, bisogna trovare quante componenti connesse esistono nel grafo. Un insieme di vertici forma una componente connessa se è possibile raggiungere ognuno di essi partendo da uno qualunque di quei vertici.Ingresso
La prima riga di input contiene due interi
v (1 ≤ v ≤ 100 000) ed e (1 ≤ e ≤ 100 000).Le successive
e righe contengono coppie di interi v1, v2 (1 ≤ v1, v2 ≤ v), indicando che il vertice v1 è connesso al vertice v2 e viceversa.Uscita
Il programma deve stampare il numero di componenti connesse del grafo.
Esempi
Ingresso | Uscita |
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