Parcours de graphes

Temps de lecture25 min

En bref

Résumé de l’article

Dans cet article, vous apprendrez à explorer un graphe en utilisant des algorithmes appelés parcours.

À retenir

  • Un parcours de graphe explore un graphe un sommet après l’autre pour construire un arbre couvrant du graphe.

  • Le parcours en profondeur (DFS) explore aussi loin que possible et revient en arrière s’il est bloqué.

  • Le parcours en largeur (BFS) explore les sommets par distance croissante depuis le point de départ.

  • Le BFS trouve le chemin le plus court dans un graphe non pondéré.

  • Terminaison, correction et complexité sont des notions importantes pour évaluer un algorithme.

  • Le BFS et le DFS ont une complexité de $O(n)$.

Contenu de l’article

1 — Vidéo

Veuillez consulter la vidéo ci-dessous (en anglais, affichez les sous-titres si besoin). Nous fournissons également une traduction du contenu de la vidéo juste après, si vous préférez.

Information

Bonjour ! Et bienvenue dans cette leçon sur le parcours de graphes.

Trouver la sortie d'un labyrinthe nécessite de parcourir une partie du labyrinthe. Le parcours de graphes est le domaine de la théorie des graphes qui décrit comment explorer un graphe, un sommet à la fois, en partant d'un sommet initial.

Dans de nombreux cas, nous nous intéressons à l’accessibilité. L’accessibilité consiste à trouver comment atteindre un sommet cible à partir d’un sommet initial, en suivant un chemin dans le graphe. Pour obtenir des chemins depuis le sommet initial vers tous les sommets accessibles, je vais vous montrer comment construire un arbre, obtenu à partir du graphe initial, qui contiendra juste assez d’informations pour nous guider vers n’importe quel sommet accessible depuis le sommet initial.

Voisins et arbres couvrants

Rappelons qu’un graphe est un couple $G$ composé d’un ensemble de sommets $V$ et d’un ensemble d’arêtes $E$. Nous devons maintenant définir quelques notions supplémentaires.

Nous définissons les voisins de $u$ dans $G$ comme l'ensemble des sommets $v$ tels que $\{u,v\}$ appartient à $E$.

Comme nous l’avons vu dans la leçon précédente, un arbre est un graphe connexe sans cycles.

Par exemple, à gauche se trouve un dessin d'un arbre. Cependant, le graphe à droite n'est pas un arbre, car il contient un cycle.

Un arbre couvrant d'un graphe $G$ est un arbre obtenu à partir de $G$ en supprimant certaines arêtes. Pour illustrer, considérons le graphe suivant. Nous pouvons obtenir un arbre couvrant en ne gardant que les arêtes suivantes.

Notez que pour un graphe donné, d'autres arbres couvrants peuvent être définis, comme celui-ci.

Trouver des arbres couvrants peut avoir de nombreuses applications. En particulier, trouver un arbre couvrant est très utile lorsque vous voulez éviter les boucles, comme dans les algorithmes de routage en réseau.

Un autre exemple de son utilité est lorsqu'il s'agit de vérifier si un graphe est connexe. Imaginez que vous voulez isoler une portion d'autoroute pour des travaux d'entretien. Tout d'abord, vous devez vous assurer que le graphe des rues reste connexe pendant les travaux.

Dans cette leçon, nous allons voir comment trouver un chemin entre deux sommets d’un graphe connexe, afin de pouvoir naviguer entre deux points quelconques.

Par définition, un arbre couvrant inclura exactement un chemin entre ces deux points.

Nous comparerons deux approches : le parcours en profondeur et le parcours en largeur.

Parcours en profondeur

L’idée principale d’un parcours en profondeur est d’explorer le graphe en sautant d’un sommet donné à l’un de ses voisins non explorés. Parfois, tous les voisins du sommet où nous nous trouvons ont déjà été explorés, auquel cas nous revenons en arrière, suivant le chemin dans la direction opposée jusqu’à trouver un sommet non exploré où sauter.

Prenons l'exemple suivant. Un parcours en profondeur, ou DFS, peut être effectué de la manière suivante. Commençons par $v_1$.

Tout d'abord, nous montons. Notez que nous aurions pu choisir d'aller à droite.

Nous continuons à explorer le graphe, nous montons à nouveau.

Ensuite, nous avons un seul voisin non exploré, qui est à droite. Nous allons donc à droite.

Maintenant, nous descendons. Alternativement, nous aurions pu continuer à droite.

À partir de là, il y a quatre voisins, dont deux non explorés. Nous choisissons d'aller à droite.

Ensuite, nous montons.

À ce stade, nous ne pouvons pas aller plus loin, car tous les voisins actuels ont déjà été explorés. Nous revenons au dernier sommet pour lequel il y avait un voisin non exploré, qui est le précédent.

Et nous descendons.

Depuis ce sommet, il ne reste qu'un seul voisin non exploré, celui de gauche. C'est le dernier sommet non exploré du graphe.

Le graphe en rouge est un arbre couvrant obtenu à partir du graphe en utilisant un DFS.

Le DFS est une stratégie simple mais efficace pour s’assurer que tous les sommets accessibles sont explorés.

C'est un moyen facile de trouver la sortie d'un labyrinthe ou de s'assurer que les rues restent connectées pendant des travaux de construction.

Cependant, elle ne garantit pas nécessairement les chemins les plus courts entre les paires de sommets du graphe. Dans cet exemple, il faut 7 sauts pour aller de $v_1$ à $v_2$, malgré le fait qu'ils pourraient être reliés en seulement 1 saut.

Parcours en largeur

L’autre approche que je vais décrire ici est le parcours en largeur. Lorsqu’on utilise un parcours en largeur, ou BFS, on explore le graphe en augmentant progressivement le nombre de sauts depuis le sommet initial.

Prenons le même exemple, où nous commençons à $v_1$.

Nous commençons par explorer tous les sommets à un saut de $v_1$ : nous connectons ainsi $v_2$ et $v_4$ à $v_1$.

Ensuite, nous explorons tous les sommets à deux sauts de $v_1$. Un sommet à deux sauts de $v_1$ est à un saut d'un sommet qui est lui-même à un saut de $v_1$. Nous regardons donc les voisins de $v_2$ et $v_4$ et les connectons à $v_2$ ou $v_4$. Nous obtenons $v_3$, $v_5$ et $v_7$.

Ensuite, nous explorons les sommets à trois sauts du sommet $v_1$. Nous regardons donc les sommets à deux sauts, qui sont $v_3$, $v_5$ et $v_7$, et leurs voisins non explorés. Nous obtenons $v_8$ et $v_6$.

Enfin, le sommet orange est à un saut de $v_8$, qui est à trois sauts du sommet $v_1$. Nous les connectons.

Le graphe résultant en rouge est un arbre couvrant obtenu à partir du BFS, composé exclusivement des plus courts chemins depuis le sommet $v_1$ vers les autres sommets du graphe.

Un BFS est une stratégie prudente dans laquelle nous essayons de maintenir les distances au sommet initial aussi petites que possible pendant l’exploration.

Cela est particulièrement utile lorsque le sommet initial contient des ressources spécifiques dont nous pourrions avoir besoin à tout moment. Cependant, cela nécessite plus d'organisation que son homologue DFS plus simple.

Comparaison entre BFS et DFS

Dans l’exemple précédent, les arbres couvrants obtenus par un BFS et un DFS sont très différents.

Voici un autre exemple utilisant le graphe que nous avons considéré plus tôt dans cette leçon.

Ceci est un arbre couvrant obtenu à partir d'un DFS en partant de $v_1$.

Tandis que ceci est un arbre couvrant obtenu à partir d'un BFS en partant de $v_1$.

Comme un BFS est effectué en augmentant progressivement les sauts depuis $v_1$, un arbre couvrant obtenu à partir d’un BFS fournira toujours le plus court chemin depuis $v_1$ vers tout autre sommet du graphe, à condition que le graphe soit non pondéré. Cela peut être clairement observé dans cet exemple.

Conclusion

Dans la prochaine leçon, nous verrons comment la différence entre un BFS et un DFS est directement liée au type de structure mémoire qui peut être utilisée pour implémenter ces deux algorithmes.

Pour aller plus loin

Lors de la conception d’un algorithme, il est très important de vérifier plusieurs aspects :

  • Terminaison – Le programme termine-t-il ? En d’autres termes, existe-t-il des scénarios dans lesquels il boucle indéfiniment ?

  • Correction – L’algorithme fait-il ce qu’il est censé faire ?

  • Complexité – Peut-on estimer le temps nécessaire à l’algorithme pour s’exécuter, en fonction de la taille de ses entrées ?

La complexité est une notion difficile à appréhender, vous en apprendrez davantage dans une séance d’algorithmique dédiée et plus tard dans le projet. Pour l’instant, considérez simplement qu’un algorithme de complexité $O(n)$ nécessite un nombre d’opérations de l’ordre de $n$.

Il existe également d’autres propriétés qui peuvent être évaluées. Par exemple, la complexité spatiale mesure l’espace mémoire nécessaire au programme, en fonction de ses entrées. Les trois propriétés listées ci-dessus sont les plus courantes. Dans les points suivants, nous allons les évaluer pour les algorithmes BFS et DFS.

2 — Propriétés du BFS

2.1 — Terminaison

L’algorithme BFS sur un graphe fini termine.

Preuve

L’algorithme visite chaque sommet atteignable une seule fois. Étant donné que le nombre de sommets est fini, l’algorithme finira par terminer.

2.2 — Correction

L’algorithme BFS retourne un chemin le plus court entre un sommet $u$ et tous les autres sommets atteignables depuis $u$ via les arêtes du graphe.

Preuve

Nous allons montrer que :

  • Tous les sommets sont visités par distance croissante depuis $u$.
  • Les chemins obtenus sont de longueur minimale.
  • Tous les sommets atteignables sont visités.

Tous les sommets sont visités par distance croissante depuis $u$

Supposons par l’absurde le premier moment où un sommet $v$ est ajouté à la file FIFO, alors qu’il existe déjà un sommet $w$ dans la file tel que $d(u, v) < d(u, w)$.

Notons $p$ le sommet voisin de $v$ qui ajoute $v$ à la FIFO. Deux cas sont possibles :

Soit $w$ est plus proche de $u$ que $p$, ce qui mène à une contradiction. En effet, lorsque $w$ a été ajouté, il y avait déjà un sommet plus éloigné dans la FIFO. Donc, ce n’est pas le premier moment où cette situation se produit. Soit la distance de $u$ à $p$ est la même que celle de $u$ à $w$. On conclut alors que $v$ est plus proche de $u$ que $p$. En considérant un prédécesseur $k$ de $v$ sur un chemin le plus court depuis $u$, on atteint une contradiction.

Les chemins obtenus sont de longueur minimale

La preuve se fait par induction. Nous montrons qu’à tout moment, tous les chemins dans la FIFO sont de longueur minimale.

Cela est trivialement vrai pour le sommet initial $u$, qui est à distance 0 de lui-même.

Comme montré précédemment, tous les sommets sont visités par distance croissante depuis $u$. Cela garantit qu’ajouter un sommet à la FIFO est toujours effectué par un voisin qui est un prédécesseur sur un chemin le plus court depuis $u$.

Tous les sommets atteignables sont visités

Par contradiction, supposons qu’un sommet $v$ atteignable n’est pas encore visité, à distance minimale de $u$. Considérons un chemin le plus court de $u$ à $v$. Notons $k$ le prédécesseur de $v$ sur ce chemin.

Ainsi, $k$ n’a pas été visité, sinon $v$ aurait été ajouté à la FIFO. Par induction, nous atteignons une contradiction.

2.3 — Complexité

L’algorithme BFS a une complexité de $O(n + m)$, où $m$ est le nombre d’arêtes du graphe et $n$ est le nombre de sommets.

Preuve

L’algorithme visite chaque sommet une seule fois et vérifie la liste des voisins non traités à chaque fois. Sa complexité est donc $O(n + m)$.

3 — Propriétés du DFS

3.1 — Terminaison

L’algorithme DFS sur un graphe fini termine.

Preuve

L’algorithme visite chaque sommet atteignable une seule fois. Étant donné que le nombre de sommets est fini, l’algorithme finira par terminer.

3.2 — Correction

L’algorithme DFS est tel qu’il visitera tous les sommets atteignables depuis $u$.

Preuve

Pour vérifier cette propriété, nous remarquons d’abord que tous les sommets visités lors d’un DFS sont effectivement atteignables. Cela peut être facilement montré par induction : $u$ est trivialement atteignable depuis lui-même, puis les sommets voisins le sont également.

Ensuite, nous devons vérifier que tous les sommets atteignables sont visités par le DFS. Raisonnons par contradiction. Un sommet $v$ atteignable est, par définition, tel qu’il existe un chemin de $u$ à $v$ dans le graphe. Sur un tel chemin, considérons le sommet juste avant $v$. Ce sommet ne peut pas être visité, sinon $v$ aurait été visité. Par induction, nous concluons que $u$ n’a pas été visité, ce qui mène à une contradiction.

3.3 — Complexité

L’algorithme DFS a une complexité de $O(n + m)$, où $m$ est le nombre d’arêtes du graphe et $n$ est le nombre de sommets.

Preuve

L’algorithme visite chaque sommet une seule fois et vérifie la liste des voisins non traités à chaque fois. Sa complexité est donc $O(n + m)$.

Pour aller encore plus loin

  • Algorithme de recherche en faisceau.

    Une variante du BFS pour l’accélérer tout en sacrifiant la garantie de trouver le chemin le plus court.

  • IDDFS.

    Une approche mixte entre DFS et BFS qui combine les avantages des deux.