Module: BFS - Camminata in larghezza


Problem

2/6

BFS: Inizio (Python)

Theory Click to read/hide

BFS (breadth-first search) è un metodo di attraversamento di grafi, molto spesso utilizzato in algoritmi sia semplici che avanzati. La ricerca in ampiezza funziona scorrendo i singoli livelli del grafico, partendo dal nodo sorgente e allontanandosi gradualmente da esso. Questo è chiaramente mostrato nell'animazione.

Per scrivere un semplice BFS, devi essere in grado di lavorare con una coda, una struttura di dati che ti permetta di prendere dall'inizio e metterlo alla fine, e anche essere in grado di memorizzare un grafico nel modulo di una lista di adiacenze.
 
Descrizione formale dell'algoritmo
1) Posiziona nella coda inizialmente vuota il numero del vertice da cui inizia la ricerca.
2) Estrai il vertice U dall'inizio della coda e contrassegnalo come utilizzato in un array separato.
3) Alla fine della coda, aggiungiamo tutti i vertici che possiamo raggiungere utilizzando lo spigolo dal vertice U e che non sono ancora segnati.
4) Se la coda è vuota, tutti i nodi del grafo connesso sono stati scansionati, altrimenti torna al passaggio 2.
 
Difficoltà di lavoro
Poiché, nel caso peggiore, l'algoritmo visita tutti i nodi del grafo, quando si memorizza il grafo sotto forma di liste di adiacenza, la complessità temporale dell'algoritmo è O(|V| + |E|), dove V è l'insieme dei vertici del grafico, ed E è l'insieme degli spigoli.  ;
In altre parole, l'algoritmo funziona nel caso peggiore per il numero di spigoli + il numero di vertici.

 

Problem

Alcuni villaggi sono collegati da strade, che possono essere rappresentate come un grafico non orientato. I vertici di questo grafico sono i villaggi e i bordi sono le strade tra i villaggi (il grafico può contenere cicli). È noto che nel villaggio S un artel Venditori ambulanti. Ogni mattina, per vendere la loro piccola merceria, i venditori ambulanti si recano in villaggi che non hanno ancora visitato, e per i quali c'è una strada da quella attuale. L'artel dei venditori ambulanti è sempre diviso in gruppi in modo che in un giorno possano fare il giro di tutti i paesi che hanno strade a partire da quello attuale.
In quanti giorni i venditori ambulanti visiteranno tutti i villaggi? Scrivi una funzione \(bfs()\) che restituirà la risposta al problema.


Inserimento
La prima riga contiene 3 numeri interi n, m, s (\(1 < = n <= 10^5\), \(0 <= m <= 10^5\), \(1 <= s <= n\)) - il numero di villaggi, il numero di strade che li collegano e il numero del villaggio in cui ha sede la banda del venditore ambulante.  ;Nelle seguenti righe m contengono 2 numeri ciascuna u, v(\(1 < = u, v <= n\ )) - numeri di due villaggi tra i quali c'è una strada. I villaggi sono indicizzati con 1.

Impressum
Stampa un solo numero: quanti giorni impiegheranno i venditori ambulanti per visitare tutti i villaggi.
 
 
Esempi
# Input Uscita
1 6 7 1
1 2
15
23
5 4
34
36
4 6		 4

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
Python
Write the program below 
def bfs():            
n, m, s = map(int, input().split())
s -= 1
used = [False] * n  # True, если были в вершине i
tm = [0] * n    # tm[i] - день, когда в деревню i пришла артель коробейников
g = []     # список смежности
for i in range(n):
    g.append([])


for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

print(bfs())

     

Program check result

To check the solution of the problem, you need to register or log in!