Parcourir un graphe en largeur

Le parcours en largeur est un type de parcours analogue au parcours en profondeur. Il permet de trouver l’ensemble des chemins les plus courts d’un nœud initial à tous les autres dans un graphe non pondéré. La façon la plus simple de l’implémenter est en utilisant des files.

Le parcours en largeur

Le parcours en largeur a pour philosophie d’aller explorer les nœuds du graphe par éloignement croissant (au sens du nombre d’arêtes minimum d’un chemin les reliant) avec un nœud de départ u.

Il permet de trouver l’ensemble des nœuds atteignables à partir de u, c’est-à-dire l’ensemble des nœuds v pour lesquels il existe un chemin reliant u à v. De plus, il permet de trouver pour tout tel v le plus court chemin entre u et v.

Dans cet exemple, le graphe utilisé est le suivant, où le nœud source est 0 (représenté sous forme d’un tableau de listes) :

012345

Retrouver le chemin à partir du parcours

Pour retrouver le chemin ayant mené du nœud initial au nœud visité, on peut créer une table de routage, qui retiendra pour tout nœud lequel l’aura ajouté à la file. Le code précédent devient :

Pour cet exemple, la table de routage affichée est [None, 0, 0, 5, 5, 0].

Une fois la table de routage trouvée, il est facile de retrouver les chemins amenant du nœud initial (ici, 0) aux autres. Si on cherche le chemin de 0 à 4 par exemple, il suffit de regarder le prédécesseur de 4, situé en routes[4]. Ce prédécesseur est 5 d’après la table de routage. On regarde donc routes[5], et on trouve 0.

Le chemin trouvé par l’algorithme pour aller de 0 à 4 est donc 0 – 5 – 4.

Propriétés de l’algorithme

Terminaison

L’algorithme ne visite qu’une fois chaque nœud atteignable, et donc termine.

Correction

L’algorithme du parcours en largeur donne le plus court chemin d’un nœud u à tous les nœuds atteignables depuis u dans le graphe.

Nous allons montrer que :

  1. Les nœuds sont visités par distance croissante au nœud u
  2. Les chemins obtenus sont de longueur minimale
  3. Tous les nœuds atteignables sont visités

Les nœuds sont visités par distance croissante au nœud u
Supposons par l’absurde le premier moment où un nœud v est ajouté à la file et est strictement plus proche de u qu’un nœud w qui y était déjà. Notons p le nœud voisin de v qui le rajoute à la file. Deux cas alors :

  • Soit w est plus proche de u que p et nous arrivons à une contradiction (lorsque w a été ajouté, il y avait un nœud dans la file plus loin, et ce n’est donc pas le premier moment où cela se produit).
  • Soit la distance de u à p est la même que celle de u à w. On en conclut que v est plus proche de u que p. Notons k un prédecesseur de v dans un chemin le plus court de u à v. On en déduit que k n’a pas été visité sinon v aurait déjà été ajouté à la file. En remontant ainsi par récurrence, on en déduit qu’un voisin direct de u n’a pas été ajouté à la file, donc que p=u, donc que v ne peut pas être plus proche de u que p.

Les chemins obtenus sont de longueur minimale
Ceci se prouve par récurrence : nous allons montrer qu’à tout moment, les chemins dans la file sont des chemins minimaux. C’est clairement vrai au départ pour le nœud initial u. Ensuite la propriété 1. nous assure qu’ajouter un nœud dans la file se fait forcément par un voisin étant un prédecesseur sur un chemin minimal depuis u.
Tous les nœuds atteignables sont visités
Notons par l’absurde v un nœud atteignable mais non visité par l’algorithme à distance minimale de u. De façon analogue, on va considérer un chemin le plus court de u à v. Notons k le prédecesseur de v sur ce chemin. On en déduit que k n’a pas été visité (sinon il aurait ajouté v à la file). Donc k est atteignable et non visité ; il est de plus plus proche de u que v. Contradiction.

Complexité

L’algorithme ne visite qu’une fois chaque sommet, et à chaque fois consulte la liste des voisins. on en déduit qu’il est en O(m)m est le nombre d’arêtes dans le graphe.

Publié le

Laisser un commentaire