%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %%
> [!nav]
> ↩ [[Code et Développement/Programmation/Graphes/Graphes|Accueil · Graphes]]
>
> | [[Code et Développement/Programmation/Graphes/02_Représentation en Python\|← Représentation en Python]] | [[Code et Développement/Programmation/Graphes/04_Parcours en profondeur (DFS)\|Parcours en profondeur – DFS →]] |
> |:---|---:|
%% nav-fin %%
# Parcours en largeur (BFS)
Ce chapitre présente le calcul du **plus court chemin** entre un sommet et tous les autres, dans un **graphe non pondéré**.
Dans un graphe non pondéré, le plus court chemin est celui qui compte le moins d'arêtes. Deux sommets peuvent être reliés par plusieurs plus courts chemins.
L'algorithme utilisé est le **parcours en largeur**, ou **BFS** pour *Breadth First Search*. Il part d'un sommet source. Il visite d'abord les voisins de la source, puis les voisins de ces voisins, et ainsi de suite. Chaque sommet est atteint par un chemin de longueur minimale.
## Le graphe étudié
Le graphe est le graphe de référence, stocké dans un dictionnaire (voir [[Code et Développement/Programmation/Graphes/02_Représentation en Python|Représentation en Python]]).
```python
D = {
'A': {'B', 'F'},
'B': {'A', 'F'},
'C': {'D', 'E', 'F'},
'D': {'C', 'E', 'G'},
'E': {'C', 'D'},
'F': {'A', 'B', 'C', 'G'},
'G': {'D', 'F'},
}
```
## La stratégie
On cherche la distance entre le sommet source A et chacun des autres sommets.
Le parcours utilise une [[Code et Développement/Programmation/Piles et Files/02_Les files|file]] : le premier sommet entré est le premier sorti.
1. On marque la source comme découverte, à distance 0, et on l'enfile.
2. On prend le sommet u en tête de file.
3. On enfile chaque voisin de u qui n'est pas encore découvert. Sa distance vaut celle de u plus 1.
4. On défile u.
5. On recommence à l'étape 2 tant que la file n'est pas vide.
Un sommet passe par trois états :
- non découvert ;
- en attente dans la file ;
- terminé, quand tous ses voisins ont été examinés.
**À manipuler :** suivez le parcours depuis A. Les voisins sont pris dans l'ordre alphabétique. Le tableau donne la distance et le parent de chaque sommet. Le parent est le sommet depuis lequel il a été découvert.
```sq-graphe
arêtes: A-B, B-F, C-D, C-E, C-F, D-E, F-G, F-A, G-D
départ: A
parcours: largeur
```
## Le programme
```python
def bfs(G, s):
distance = {s: 0} # sommets découverts et leur distance à s
file = [s]
while file: # tant que la file n'est pas vide
u = file.pop(0) # on défile le sommet en tête
for v in sorted(G[u]):
if v not in distance: # v n'est pas encore découvert
distance[v] = distance[u] + 1
file.append(v) # on enfile v
return distance
print(bfs(D, 'A'))
```
Ce programme affiche :
```
{'A': 0, 'B': 1, 'F': 1, 'C': 2, 'G': 2, 'D': 3, 'E': 3}
```
`sorted(G[u])` parcourt les voisins dans l'ordre alphabétique. Un ensemble Python n'a pas d'ordre fixe : sans `sorted`, l'ordre de découverte peut changer d'une exécution à l'autre. Les distances, elles, ne changent pas.
Le dictionnaire `distance` sert aussi à savoir si un sommet est déjà découvert. Un sommet n'est donc enfilé qu'une seule fois.
`file.pop(0)` décale tous les éléments de la liste. Pour une grande file, le module `collections` fournit `deque`, dont la méthode `popleft()` défile sans décalage.
## L'arbre du parcours
Pour retrouver les chemins eux-mêmes, on enregistre le **parent** de chaque sommet : le sommet depuis lequel il a été découvert.
```python
def bfs_parents(G, s):
parent = {s: None}
file = [s]
while file:
u = file.pop(0)
for v in sorted(G[u]):
if v not in parent:
parent[v] = u
file.append(v)
return parent
print(bfs_parents(D, 'A'))
```
Ce programme affiche :
```
{'A': None, 'B': 'A', 'F': 'A', 'C': 'F', 'G': 'F', 'D': 'C', 'E': 'C'}
```
Le plus court chemin de A vers E se lit en remontant les parents depuis E : E, C, F, A. Dans l'ordre, A → F → C → E.
Les arêtes entre chaque sommet et son parent forment un arbre couvrant : l'**arbre du parcours en largeur**. Dans cet arbre, la profondeur de chaque sommet est sa distance à A.
**À manipuler :** déroulez le parcours, puis cliquez sur « Arbre du parcours ». Seules les arêtes de l'arbre restent visibles.
```sq-graphe
arêtes: A-B, B-F, C-D, C-E, C-F, D-E, F-G, F-A, G-D
départ: A
parcours: largeur
```
## Avec networkx
Le module `networkx` fournit le parcours en largeur. `nx.bfs_tree` renvoie l'arbre du parcours. `nx.bfs_edges` renvoie ses arêtes, dans l'ordre de découverte.
```python
import networkx as nx
G = nx.Graph(D)
print(list(nx.bfs_edges(G, 'A')))
```
Ce programme affiche par exemple :
```
[('A', 'B'), ('A', 'F'), ('F', 'C'), ('F', 'G'), ('C', 'D'), ('C', 'E')]
```
L'ordre des arêtes de même distance peut varier, car il suit l'ordre des ensembles du dictionnaire.
## Graphe orienté
Le parcours en largeur fonctionne aussi sur un graphe orienté. Les voisins d'un sommet sont alors les sommets vers lesquels partent ses flèches.
```python
D = {
'A': {'B'},
'B': {'F'},
'C': {'D', 'E', 'F'},
'D': {'E'},
'E': set(),
'F': {'A', 'G'},
'G': {'D'},
}
print(bfs(D, 'A'))
```
Ce programme affiche :
```
{'A': 0, 'B': 1, 'F': 2, 'G': 3, 'D': 4, 'E': 5}
```
Aucune flèche n'arrive sur C : C n'est atteint par aucun chemin depuis A. Il n'apparaît pas dans le résultat.
**À manipuler :** à la fin du parcours, C reste grisé.
```sq-graphe
arêtes: A>B, B>F, C>D, C>E, C>F, D>E, F>G, F>A, G>D
départ: A
parcours: largeur
```
Le parcours en largeur ne tient pas compte des poids. Pour un graphe pondéré, le plus court chemin se calcule avec l'[[Code et Développement/Programmation/Graphes/05_Algorithme de Dijkstra|algorithme de Dijkstra]].
%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %%
> [!nav]
> ↩ [[Code et Développement/Programmation/Graphes/Graphes|Accueil · Graphes]]
>
> | [[Code et Développement/Programmation/Graphes/02_Représentation en Python\|← Représentation en Python]] | [[Code et Développement/Programmation/Graphes/04_Parcours en profondeur (DFS)\|Parcours en profondeur – DFS →]] |
> |:---|---:|
%% nav-fin %%