Graph traversal

Reading time25 min

En bref

Résumé de l’article

Dans cet article, vous apprendrez comment naviguer dans un graphe, en utilisant des algorithmes appelés parcours.

Principaux points à retenir

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

  • La recherche en profondeur (DFS) va aussi loin que possible puis revient en arrière lorsqu’elle est bloquée.

  • La recherche en largeur (BFS) explore les sommets par ordre croissant de distance depuis le départ.

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

  • La terminaison, la correction et la complexité sont des notions importantes pour évaluer un algorithme.

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

Contenu de l’article

1 — Vidéo

Veuillez consulter la vidéo ci-dessous. Vous pouvez également lire la transcription si vous préférez.

Information

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

Trouver la sortie d'un labyrinthe nécessite de parcourir une partie du labyrinthe. Le parcours de graphe 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 depuis un sommet initial, en suivant un chemin dans le graphe. Pour obtenir les chemins du sommet initial à tous les sommets accessibles, je vais vous montrer comment construire un arbre, obtenu à partir du graphe initial, qui transmettra 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.

Maintenant, 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 conservant 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 lors de l'évaluation de la connexité d'un graphe. Imaginez que vous souhaitez isoler une portion d'autoroute pour des travaux de maintenance. D'abord, vous devez vous assurer que le graphe des rues reste connecté 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 n’importe quels deux points.

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

Nous comparerons deux approches : la recherche en profondeur et la recherche en largeur.

Recherche en profondeur

L’idée principale d’une recherche en profondeur est de continuer à 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 sommes ont déjà été explorés, auquel cas nous revenons en arrière, suivant la trace dans la direction opposée jusqu’à trouver un sommet non exploré vers lequel sauter.

Prenons l'exemple suivant. Une recherche en profondeur, ou DFS, peut être réalisée de la manière suivante. Commençons depuis $v_1$.

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

Nous continuons à explorer le graphe, nous montons encore.

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

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

À partir d'ici, il y a quatre voisins, dont deux sont 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é, qui est celui à gauche. C'est le dernier sommet non exploré dans le graphe.

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

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 les travaux.

Cependant, cela ne donne pas nécessairement les chemins les plus courts entre les paires de sommets dans le graphe. Dans cet exemple, il faut 7 sauts pour aller de $v_1$ à $v_2$, alors qu'ils pourraient être reliés en un seul saut.

Recherche en largeur

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

Considérons le même exemple, où nous commençons en $v_1$.

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

Puis 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 à 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, qui est composé exclusivement de chemins les plus courts du sommet $v_1$ aux autres sommets du graphe.

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

Ceci 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 démarrant de $v_1$.

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

Parce qu’un BFS est réalisé en augmentant progressivement les sauts depuis $v_1$, un arbre couvrant obtenu par BFS fournira toujours le chemin le plus court de $v_1$ à n’importe quel autre sommet du graphe, à condition que le graphe soit non pondéré. Cela est clairement visible dans cet exemple.

Mots de 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 se 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 session de programmation 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 ne visite qu’une seule fois chaque sommet atteignable. Puisque le nombre de sommets est fini, l’algorithme terminera donc éventuellement.

2.2 — Correction

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

Preuve

Nous allons montrer que :

  • Tous les sommets sont visités dans l’ordre croissant de leur distance à $u$.
  • Les chemins obtenus sont de longueur minimale.
  • Tous les sommets atteignables sont visités.

Tous les sommets sont visités dans l’ordre croissant de leur distance à u

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

Notons $p$ le sommet, voisin de $v$, qui ajoute $v$ à la FIFO. Il y a deux cas :

Soit $w$ est plus proche de $u$ que $p$ et nous obtenons une contradiction. En effet, lorsque $w$ a été ajouté, il y avait déjà un sommet dans la FIFO qui était plus éloigné. Donc ce n’est pas le premier moment où cette situation se produit. Ou la distance de $u$ à $p$ est la même que celle de $u$ à $w$. Nous concluons donc que $v$ est plus proche de $u$ que $p$. Soit $k$ un prédécesseur de $v$ sur un chemin le plus court de $u$ à $v$. $k$ n’a pas été visité, sinon $v$ l’aurait ajouté à la FIFO. Par récurrence, on voit qu’un voisin direct de $u$ n’a pas été ajouté à la FIFO, donc $p = u$. $v$ ne peut donc pas être plus proche de $u$ que $p$.

Les chemins obtenus sont de longueur minimale

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

C’est trivialement vrai pour le sommet de départ $u$, car il est à distance 0 de lui-même.

Comme montré précédemment, tous les sommets sont visités dans l’ordre croissant de leur distance à $u$. Cela garantit que l’ajout d’un sommet à la FIFO est toujours effectué par un voisin qui est un prédécesseur sur un chemin le plus court initié depuis $u$.

Tous les sommets atteignables sont visités

Par contradiction, soit $v$ un sommet atteignable, mais pas encore visité, à distance minimale de $u$. Considérons un chemin le plus court de $u$ à $v$. Soit $k$ le prédécesseur de $v$ sur ce chemin.

Ainsi, $k$ n’a pas été visité, sinon il aurait été ajouté à la FIFO. Donc $k$ est atteignable et pas encore visité, et est plus proche de $u$ que $v$. Nous obtenons une contradiction.

2.3 — Complexité

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

Preuve

L’algorithme ne visite qu’une seule fois chaque sommet, et vérifie la liste des voisins non traités à chaque fois. Par conséquent, sa complexité est $O(n + m)$.

3 — Propriétés du DFS

3.1 — Terminaison

L’algorithme DFS sur un graphe fini termine.

Preuve

L’algorithme ne visite qu’une seule fois chaque sommet atteignable. Puisque le nombre de sommets est fini, l’algorithme terminera donc éventuellement.

3.2 — Correction

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

Preuve

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

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

3.3 — Complexité

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

Preuve

L’algorithme ne visite qu’une seule fois chaque sommet, et vérifie la liste des voisins non traités à chaque fois. Par conséquent, sa complexité est $O(n + m)$.

Pour aller plus loin

  • Beam search.

    Une variation 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 le meilleur des deux mondes.