Module: BFS - Camminata in larghezza


Problem

1/6

BFS: Inizio (C++)

Theory Click to read/hide

Ricerca in ampiezza (BFS)
BFS (breadth-first search,breadth-first search) - un metodo di attraversamento di grafi, molto spesso utilizzato sia in algoritmi 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 il BFS  più semplice, devi essere in grado di lavorare con una struttura di dati che ti permetta di prendere dall'inizio e metterlo alla fine, ed essere anche in grado di memorizzare il grafico sotto forma di lista di adiacenza (cioè con una coda ).
 
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 etichettati.
4) Se la coda è vuota, tutti i nodi del grafo connesso sono stati scansionati, altrimenti torna al passaggio 2.
 
Complessità
Poiché l'algoritmo visita tutti i nodi del grafo nel caso peggiore, quando si memorizza il grafo come liste di adiacenza, la complessità temporale dell'algoritmo è O(|V| + |E|) , dove V è l'insieme dei vertici del grafo, e E è l'insieme degli spigoli. In altre parole, l'algoritmo funziona nel caso peggiore per numero di spigoli + 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 all'attività.

 
Input
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
C++
Write the program below 
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>

using namespace std;

vector<bool> used;   
// used[i] = true, если мы были в вершине i
vector<vector<int> > g;   // список смежности
vector<int> tm;     
// tm[i] - день, когда в деревню i 
// пришла артель коробейников
int n, m, s;

int bfs()
{                   
}

int main()
{
	cin >> n >> m >> s;
	s--;
	g.resize(n);
	tm.resize(n);
	used.assign(n, false);
	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	cout << bfs();
	return 0;
}

     

Program check result

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