Algorithme de Breadth First Search (BFS)
Imaginez qu’avec un graphe composé de
n sommets et de e arêtes, vous souhaitiez partir d’un sommet et parcourir progressivement tout le graphe, en visitant tous les sommets atteignables à partir de ce point de départ. Plusieurs approches sont possibles, et l’une des plus courantes est l’algorithme de recherche en largeur, appelé BFS (Breadth-First Search). De par sa nature, BFS permet de calculer la distance la plus courte entre le sommet source et tous les autres sommets du graphe, ce qui le rend très utile dans de nombreuses applications.
Une manière très utile d’imaginer l’algorithme BFS consiste à visualiser un « incendie » qui se propage à travers le graphe. Supposez que chaque sommet du graphe a besoin d’une minute pour « brûler ». Une fois qu’il a complètement brûlé, il enflamme tous ses voisins immédiats, qui à leur tour brûlent pendant une minute avant de propager l’incendie, et ainsi de suite.
On commence donc par « enflammer » le sommet de départ. Ensuite, le feu se propage à tous ses voisins. Au bout d’une minute, le feu gagne les voisins de ces derniers, puis ceux de leurs propres voisins, et ainsi de suite. Le processus se poursuit jusqu’à ce qu’il ne reste plus aucun sommet à brûler. Cette image mentale facilite grandement la compréhension de l’implémentation de BFS.
L’implémentation de BFS peut se faire grâce à une
queue (file) et à une liste de sommets qui servent à garder la trace de ceux qui ont déjà « brûlé » (used) :from collections import deque
n, e = map(int, input().split()) # n : nombre de sommets, e : nombre d'arêtes
g = [[] for _ in range(n)] # liste d'adjacence du graphe
for _ in range(e): # lire les arêtes
a, b = map(int, input().split()) # a -> b et b -> a
g[a].append(b)
g[b].append(a)
start = int(input()) # sommet de départ
used = [False] * n # sommets déjà visités
q = deque([start]) # file de sommets
used[start] = True # marquer le sommet de départ comme visité
while q: # tant que la file n'est pas vide
v = q.popleft() # retirer un sommet de la file
print(v, end=' ') # afficher le sommet
for to in g[v]: # pour chaque sommet connecté à v
if not used[to]: # si le sommet n'a pas encore été visité
q.append(to) # on l'ajoute à la file
used[to] = True # et on le marque comme visitéIci, nous initialisons d’abord le graphe et débutons le parcours à partir du sommet
start. Au départ, tous les éléments de used sont à False. Une fois qu’un sommet est visité, nous l’ajoutons à la file et le marquons comme visité. C’est ainsi que nous reproduisons la « combustion » du graphe. À chaque itération, nous ajoutons à la file tous les sommets adjacents qui n’ont pas encore été visités, puis nous les marquons comme utilisés.Passons maintenant à la simulation de l’algorithme sur plusieurs entrées :
n = 4, e = 4
Les paires
a, b d’entrée sont les suivantes : [(0, 1), (0, 2), (1, 2), (3, 2)]Le sommet de départ est 3
used = [False, False, False, True],q = [3]
v = 3,q = []→ ajouter tous les voisins non visités à la file
used = [False, False, True, True],q = [2]
v = 2,q = []→ ajouter tous les voisins non visités à la file
used = [True, True, True, True],q = [0, 1]
v = 0,q = [1]→ ajouter tous les voisins non visités à la file
v = 1,q = []→ ajouter tous les voisins non visités à la file
- Terminé
n = 5, e = 4
Les paires
a, b d’entrée sont les suivantes : [(0, 1), (0, 2), (1, 2), (3, 4)]Le sommet de départ est 0
used = [True, False, False, False, False],q = [0]
v = 0,q = []→ ajouter tous les voisins non visités à la file
used = [True, True, True, False, False],q = [1, 2]
v = 1,q = [2]→ ajouter tous les voisins non visités à la file
v = 2,q = []→ ajouter tous les voisins non visités à la file
- Terminé
Notice how nodes 3 and 4 were never visited.
They were not connected to the initial node 0.
Défi : Compter le nombre de composantes connectées dans un graphe
Étant donné un graphe non orienté avec
v sommets et e arêtes, on vous demande de calculer le nombre de composantes connectées dans ce graphe. Un ensemble de sommets forme une composante connectée si l’on peut circuler entre eux.Entrée
La première ligne de l’entrée contient deux entiers
v (1 ≤ v ≤ 100 000) et e (1 ≤ e ≤ 100 000).Les
e lignes suivantes contiennent des paires d’entiers v1, v2 (1 ≤ v1, v2 ≤ v), indiquant que le sommet v1 est connecté au sommet v2, et inversement.Sortie
Le programme doit afficher le nombre de composantes connectées dans le graphe.
Exemples
Input | Output |
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