Module: BFS - Marche de la largeur


Problem

2/6

BFS : Début (Python)

Theory Click to read/hide

BFS (Breadth-First Search) est une méthode de parcours de graphe, très souvent utilisée dans les algorithmes simples et avancés. La recherche étendue d'abord fonctionne en parcourant les niveaux individuels du graphique, en commençant par le nœud source et en s'en éloignant progressivement. Ceci est clairement montré dans l'animation.

Pour écrire un BFS simple, vous devez être capable de travailler avec une file d'attente, une structure de données qui vous permet de prendre du début et de la mettre à la fin, et également de pouvoir stocker un graphique sous la forme d'une liste de contiguïté.
 
Description formelle de l'algorithme
1) Placer le numéro du sommet à partir duquel la recherche commence dans la file d'attente initialement vide.
2) Extrayez le sommet U du début de la file d'attente et marquez-le comme utilisé dans un tableau séparé.
3) A la fin de la file d'attente, ajouter tous les sommets que l'on peut atteindre en utilisant l'arête du sommet U et qui ne sont pas encore marqués.
4) Si la file d'attente est vide, alors tous les nœuds du graphe connexe ont été scannés, sinon retournez à l'étape 2.
 
Difficulté de travail
Puisque, dans le pire des cas, l'algorithme visite tous les nœuds du graphe, lors du stockage du graphe sous forme de listes d'adjacence, la complexité temporelle de l'algorithme est O(|V| + |E|), où V est l'ensemble des sommets du graphe, et E est l'ensemble des arêtes.  ;
En d'autres termes, l'algorithme fonctionne dans le pire des cas pour le nombre d'arêtes + le nombre de sommets.

 

Problem

Certains villages sont reliés par des routes, qui peuvent être représentées sous la forme d'un graphe non orienté. Les sommets de ce graphe sont des villages, et les arêtes sont des routes entre villages (le graphe peut contenir des cycles). On sait que dans le village S un artel Colporteurs. Tous les matins, pour vendre leur petite mercerie, les colporteurs se rendent dans des villages qu'ils n'ont pas encore visités, et auxquels il existe une route depuis l'actuel. L'artel des colporteurs est toujours divisé en groupes afin qu'ils puissent faire le tour de tous les villages qui ont des routes depuis l'actuel en une journée.
Dans combien de jours les colporteurs visiteront-ils tous les villages ? Écrivez une fonction \(bfs()\) qui renverra la réponse au problème.


Entrée
La première ligne contient 3 entiers n, m, s (\(1 < = n <= 10^5\), \(0 <= m <= 10^5\), \(1 <= s <= n\)) - le nombre de villages, le nombre de routes entre eux et le numéro du village dans lequel le gang de colporteurs est basé.  ;Dans les lignes m suivantes contiennent 2 nombres chacun u, v(\(1 < = u, v <= n\ )) - numéros de deux villages entre lesquels il y a une route. Les villages sont indexés avec 1.

Mentions légales
Imprimez un seul chiffre - combien de jours il faudra aux colporteurs pour visiter tous les villages.
 
 
Exemples
# Entrée Sortie
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!