Lunghezza del percorso più breve con BFS
Poiché l’algoritmo BFS parte da un nodo e si espande gradualmente visitando i vicini, è possibile trovare il percorso più breve dal nodo iniziale a tutti gli altri nodi del grafo. Per ottenere questo risultato, occorre apportare una piccola modifica all’algoritmo di base. Introdurremo un array delle distanze
d, inizialmente impostato tutto a -1. Se il valore in d di un vertice è -1, significa che quel vertice non è stato ancora visitato. Se invece è un valore positivo, indica la distanza del vertice corrente dal nodo iniziale: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): # lettura degli 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
d = [-1] * n # distanza dal vertice di partenza
q = deque([start]) # coda di vertici
d[start] = 0 # distanza dal vertice di partenza a se stesso è 0
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 ciascun vertice collegato a v
if d[to] == -1: # se il vertice non è ancora visitato
d[to] = d[v] + 1 # (start -> to) = (start -> v) + 1
q.append(to) # aggiungi il vertice alla coda
print(d)In questo esempio, inizializziamo
d con -1, in modo da indicare che nessun vertice è stato ancora visitato. Quindi impostiamo d[start] a 0, il che significa che la distanza tra il vertice start e se stesso è 0.Man mano che l’algoritmo elabora i nodi, i relativi valori nell’array
d vengono aggiornati, fornendo la distanza di ogni nodo dal vertice start.Osserviamo il funzionamento dell’algoritmo su alcuni input di esempio:
n = 4, e = 4
La coppia di input
a, b è la seguente: [(0, 1), (0, 2), (1, 2), (3, 2)]Il vertice di partenza è 3
d = [-1, -1, -1, 0],q = [3]
v = 3,q = []→ aggiungi tutti i vicini non ancora usati alla coda
d = [-1, -1, 1, 0],q = [2]
v = 2,q = []→ aggiungi tutti i vicini non ancora usati alla coda
d = [2, 2, 1, 0],q = [0, 1]
v = 0,q = [1]→ aggiungi tutti i vicini non ancora usati alla coda
v = 1,q = []→ aggiungi tutti i vicini non ancora usati alla coda
- Fine
n = 5, e = 4
La coppia di input
a, b è la seguente: [(0, 1), (0, 2), (1, 2), (3, 4)]Il vertice di partenza è 0
d = [0, -1, -1, -1, -1],q = [0]
v = 0,q = []→ aggiungi tutti i vicini non ancora usati alla coda
d = [0, 1, 1, -1, -1],q = [1, 2]
v = 1,q = [2]→ aggiungi tutti i vicini non ancora usati alla coda
v = 2,q = []→ aggiungi tutti i vicini non ancora usati alla coda
- Fine
Notice how nodes 3 and 4 were never visited.
They were not connected to the initial node 0.
Sfida: Trovare la lunghezza del percorso più breve
Dato un grafo non orientato con
v vertici e e archi, si richiede di calcolare la lunghezza del percorso più breve tra il vertice 1 e il vertice v. Se non esiste un collegamento tra di loro, il programma deve stampare Impossible.Input
La prima riga di input contiene due interi
v (1 ≤ v ≤ 100 000) ed e (1 ≤ e ≤ 100 000).Le successive
e righe contengono una coppia di interi v1, v2 (1 ≤ v1, v2 ≤ v) che indicano che il vertice v1 è collegato al vertice v2 e viceversa.Output
Il programma deve stampare la lunghezza del percorso più breve tra
1 e v.Esempi
Ingresso | Uscita |
5 6
1 2
2 3
1 3
3 4
4 3
3 5 | 2 |
2 1
1 2 | 1 |
2 0 | Impossible |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB