Traversées de graphes
La traversée de graphes signifie visiter chaque sommet et chaque arête exactement une fois dans un puits -ordre défini. Lors de lutilisation de certains algorithmes graphiques, vous devez vous assurer que chaque sommet du graphique est visité exactement une fois. Lordre dans lequel les sommets sont visités est important et peut dépendre de lalgorithme ou de la question que vous résolvez.
Lors dun parcours, il est important que vous suiviez les sommets visités. Le moyen le plus courant de suivre les sommets est de les marquer.
Breadth First Search (BFS)
Il existe de nombreuses façons de parcourir les graphiques. BFS est lapproche la plus couramment utilisée.
BFS est un algorithme de traversée où vous devez commencer à traverser à partir dun nœud sélectionné (nœud source ou nœud de départ) et traverser le graphe par couches explorant ainsi les nœuds voisins (nœuds qui sont directement connectés au nœud source). Vous devez ensuite vous déplacer vers les nœuds voisins de niveau suivant.
Comme le nom BFS lindique, vous devez parcourir le graphe dans le sens de la largeur comme suit:
- Déplacez-vous dabord horizontalement et visiter tous les nœuds du calque actuel
- Passer au calque suivant
Considérez le diagramme suivant. 
La distance entre les nœuds de la couche 1 est comparativement inférieure à la distance entre les nœuds de la couche 2. Par conséquent, dans BFS, vous devez traverser tous les nœuds de la couche 1 avant de vous déplacer vers les nœuds de la couche 2.
Traversée des nœuds enfants
Un graphique peut contenir des cycles, ce qui peut vous ramener au même nœud en parcourant le graphique. Pour éviter de traiter à nouveau le même nœud, utilisez un tableau booléen qui marque le nœud après son traitement. Lors de la visite des nœuds dans la couche dun graphe, stockez-les de manière à pouvoir parcourir les nœuds enfants correspondants dans un ordre similaire.
Pour faciliter ce processus, utilisez une file dattente pour stocker le nœud et marquez-le comme « visité » jusquà ce que tous ses voisins (les sommets qui lui sont directement connectés) soient marqués. La file dattente suit la méthode de mise en file dattente First In First Out (FIFO), et par conséquent, les voisins du nœud seront visités dans lordre dans lequel ils ont été insérés dans le nœud, cest-à-dire que le nœud qui a été inséré en premier sera visité en premier, et ainsi sur.
Pseudocode
Processus de déplacement 
Le parcours commencera à partir du nœud source et mettra les s en file dattente. s sera marqué comme « visité ».
Première itération
- s seront sortis de la file dattente
- Les voisins de s ie 1 et 2 seront traversés
- 1 et 2, qui nont pas été parcourus auparavant, sont parcourus. Ils seront:
- Poussés dans la file dattente
- 1 et 2 seront marqués comme visités
Deuxième itération
- 1 est sorti de la file dattente
- Les voisins de 1 ie s et 3 sont traversés
- s est ignoré car il est marqué comme « visité »
- 3, qui na pas été parcouru auparavant, est parcouru. Il est:
- Poussé dans la file dattente
- Marqué comme visité
Troisième itération
- 2 est sorti de la file dattente
- Les voisins de 2 cest-à-dire que s, 3 et 4 sont traversés
- 3 et s sont ignorés car ils sont marqués comme « visités »
- 4, qui na pas été parcouru auparavant, est parcouru. Il est:
- Poussé dans la file dattente
- Marqué comme visité
Quatrième itération
- 3 est sorti de la file dattente
- Les voisins de 3 cest-à-dire 1, 2 et 5 sont traversés
- 1 et 2 sont ignorés car ils sont marqués comme « visités »
- 5, qui na pas été parcouru auparavant, est parcouru. Il est:
- Poussé dans la file dattente
- Marqué comme visité
Cinquième itération
- 4 sera sorti de la file dattente
- Voisins de 4 cest-à-dire que 2 est traversé
- 2 est ignoré car il est déjà marqué comme « visité »
Sixième itération
- 5 est sorti de la file dattente
- Voisins de 5 cest-à-dire que 3 est traversé
- 3 est ignoré car il est déjà marqué comme « visité »
La file dattente est vide et elle sort de la boucle. Tous les nœuds ont été parcourus en utilisant BFS.
Si toutes les arêtes dun graphe ont le même poids, alors BFS peut également être utilisé pour trouver la distance minimale entre les nœuds dans un graphe.
Exemple
Comme dans ce diagramme, partez du nœud source, pour trouver la distance entre la source nœud et nœud 1. Si vous ne suivez pas lalgorithme BFS, vous pouvez passer du nœud source au nœud 2 puis au nœud 1. Cette approche calculera la distance entre le nœud source et le nœud 1 comme 2, alors que le minimum la distance est en fait 1. La distance minimale peut être calculée correctement en utilisant lalgorithme BFS.
Complexité
La complexité temporelle de BFS est O (V + E), où V est le nombre de nœuds et E est le nombre darêtes.
Applications
1. Comment déterminer le niveau de chaque nœud dans larborescence donnée?
Comme vous le savez dans BFS, vous parcourez les niveaux. Vous pouvez également utiliser BFS pour déterminer le niveau de chaque nœud.
Implémentation
Ce code est similaire au code BFS avec seulement la différence suivante:
level] = level + 1;
Dans ce code, lorsque vous visitez chaque nœud, le niveau de ce nœud est défini avec un incrément du niveau de son nœud parent. Cest ainsi que le niveau de chaque nœud est déterminé.
2 . 0-1 BFS
Ce type de BFS est utilisé pour trouver la distance la plus courte entre deux nœuds dans un graphe à condition que les arêtes du graphe aient les poids 0 ou 1. Si vous appliquez le BFS expliqué plus haut dans cet article, vous obtiendrez un résultat incorrect pour la distance optimale entre 2 nœuds.
Dans cette approche, un tableau booléen nest pas utilisé pour marquer le nœud car la condition de la distance optimale sera vérifiée lorsque vous visitez chaque nœud. Une file dattente à deux extrémités est utilisée pour stocker le nœud. Dans 0-1 BFS, si le poids du bord = 0, alors le nœud est poussé vers lavant de la sortie de file. Si le poids du bord = 1, alors le nœud est poussé vers larrière de la sortie de file.
Implémentation
Q est une file dattente à deux extrémités. La distance est un tableau où, distance contiendra la distance entre le nœud de départ et le nœud v. Initialement, la distance définie entre le nœud source et chaque nœud est linfini.
Comprenons ce code avec le graphique suivant:
La liste de contiguïté du graphe sera la suivante:
Ici « s » est considéré comme 0 ou le nœud source.
0 – > 1 – > 3 – > 2
bords.first = 1, bords.second = 1
bords.first = 3, bords.second = 0
bords.first = 2, bords.second = 1
1 – > 0 – > 4
bords.first = 0, bords.second = 1
bords.first = 4 , bords.second = 0
2 – > 0 – > 3
bords.first = 0 , bords.second = 0
bords.first = 3, bords.second = 0
3 – > 0 – > 2 – > 4
bords.first = 0, bords.second = 0
bords.first = 2, bords.second = 0
bords.first = 4, bords.second = 0
4 – > 1 – > 3
bords.first = 1, bords.second = 0
bords.first = 3, bords.second = 0
Si vous utilisez lalgorithme BFS, le résultat sera incorrect car il vous montrera la distance optimale entre s et noeud 1 et s et noeud 2 comme 1 respectivement. En effet, il visite les enfants de s et calcule la distance entre s et ses enfants, qui est de 1. La distance optimale réelle est de 0 dans les deux cas.
Traitement
En partant du nœud source, cest-à-dire 0, il se déplacera vers 1, 2 et 3. Puisque le poids darête entre 0 et 1 et 0 et 2 est 1 respectivement , 1 et 2 seront poussés à larrière de la file dattente. Cependant, puisque le poids de bord entre 0 et 3 est 0, 3 sera poussé au début de la file dattente. La distance sera maintenue dans le tableau de distance en conséquence.
3 sera alors sorti de la file dattente et le même processus sera appliqué à ses voisins, et ainsi de suite.