Algorithmes de parcours

Les parcours en largeur et en profondeur des graphes généralisent les parcours similaires dans les arbres. Ces algorithmes servent à rechercher des chemins et des cycles dans un graphe, à déterminer les composantes connexes, etc. Ils nous serviront souvent en tant que procédures de base pour d’autres algorithmes.
Lors d’un parcours, un sommet a trois états possibles :
– non_atteint – l’algorithme n’a pas encore rencontré ce sommet ;
– atteint – le sommet a été rencontré, mais nous n’en avons pas fini avec lui ;
– traité – le sommet a été traité, nous avons parcouru toutes les arêtes incidentes à ce sommet (ou les arcs sortants, s’il s’agit d’un graphe orienté).
En plus de son état, chaque sommet x recevra un numéro σ[x], qui correspond à l’ordre du parcours. Enfin, pour chaque sommet x on garde le pere[x], à savoir le sommet duquel nous sommes venus lorsque nous avons atteint x pour la première fois. Cette arborescence pourra s’avérer bien utile par la suite !

Parcours en largeur

L’algorithme

Lorsque l’on fait un parcours en largeur à partir d’un sommet x, on atteint d’abord les voisins de x, ensuite les voisins des voisins (sauf ceux qui sont déjà atteints) et ainsi de suite. C’est pourquoi le parcours en largeur est aussi appelé parcours concentrique. Il sert notamment à le recherche des plus courts chemins dans un graphe. Une description détaillée du parcours en largeur est donnée dans l’algorithme 2.1.

Complexité

Si le graphe est donné par tableau de listes de successeurs, la complexité du parcours en largeur est O(n + m).

Exercices

1. Modifier l’algorithme de parcours en largeur afin de récupérer les composantes connexes du graphe en entrée.
Algorithme 2.1 : Parcours en largeur
Entrée : un graphe G = (X, A)
Sortie : un ordre σ sur les sommets et une arborescence debut
// Initialisation pour chaque x ∈ X
etat[x] ← non_atteint
index ← 1
a_traiter ← ∅ // a_traiter est une FILE
// Boucle principale
pour chaque z ∈ X
si etat[z] = non_atteint
// On lance un parcours à partir de z pere[z] ← nil
σ[z] ← index
index + +
a_traiter ← a_traiter ∪ {z}
tant_que a_traiter = ∅
x ← T ete(a_traiter)
pour chaque y ∈ (x)
si etat[y] = non_atteint
etat[y] ← atteint
pere[y] ← x
σ[y] ← index
index + +
a_traiter ← a_traiter ∪ {y}
a_traiter ← a_traiter − {x}
etat[x] ← traite
fin
2. Appliquer le parcours en largeur à la recherche d’un plus court chemin entre deux som-mets x et y du graphe G.
3. Proposer une version du parcours en largeur où la file a_traiter est simulée à l’aide d’un
tableau de n éléments. Il suffira de garder deux variables, deb et f in, qui pointeront sur le premier et respectivement le dernier élément à traiter.

Parcours en profondeur

L’algorithme

Contrairement au parcours en largeur, lorsque l’on fait un parcours en profondeur à partir d’un sommet x on tente d’avancer le plus loin possible dans le graphe, et ce n’est que lorsque toutes les possibilités de progression sont bloquées que l’on revient (étape de backtrack) pour explorer un nouveau chemin ou une nouvelle chaîne. Le parcours en profondeur correspond aussi à l’exploration d’un labyrinthe. L’algorithme 2.2 propose une implantation récursive du parcours en profondeur.
Les applications de ce parcours sont peut-être moins évidentes que pour le parcours en largeur, mais le parcours en profondeur permet de résoudre efficacement des problèmes plus difficiles comme la recherche de composantes fortement connexes dans un graphe orienté, le test de planarité, etc.
Algorithme 2.2 : Parcours en profondeur
Entrée : un graphe G = (X, A)
Sortie : un ordre σ sur les sommets et une arborescence
var index : entier
procedure parcours_prof_recursif(sommet x)
debut
etat[x] ← atteint
σ [x] ← index index + +
pour chaque y ∈ (x)
si etat[y] = non_atteint
pere[y] ← x
parcours_prof_recursif(y)
etat[x] ← traite
fin
debut
// Initialisation pour chaque x ∈ X
etat[x] ← non_atteint
index ← 1
// Boucle principale
pour chaque x ∈ X
si etat[x] = non_atteint
// On lance un parcours à partir de x pere[x] ← nil parcours_prof_recursif(x)
fin

Complexité

Comme pour le parcours en largeur, si le graphe est donné par tableau de listes de succes-seurs, la complexité du parcours en profondeur est O(n + m).

Exercices

1. Modifier l’algorithme de parcours en profondeur afin de récupérer les composantes connexes du graphe.
2. Appliquer le parcours en profondeur à la recherche d’un chemin entre deux sommets x et y.
3. Utiliser le parcours en profondeur pour chercher un cycle dans un graphe non-orienté.
4. Proposer une implantation non récursive du parcours en profondeur. On pourra utiliser une structure très semblable à l’algorithme de parcours en largeur, où la file a_traiter sera remplacée par une pile.

I Algorithmes de base
1 Généralités
1.1 Définitions et notations
1.2 Structures de données pour la représentation des graphes
1.2.1 Matrice d’adjacence
1.2.2 Tableau de listes des successeurs
2 Algorithmes de parcours
2.1 Parcours en largeur
2.1.1 L’algorithme
2.1.2 Complexité
2.1.3 Exercices
2.2 Parcours en profondeur
2.2.1 L’algorithme
2.2.2 Complexité
2.2.3 Exercices
3 Graphes orientés sans circuits. Tri topologique
4 Plus courts chemins dans un graphs
5 Arbre recouvrent de poids minimum
6 Flots et réseaux de transport
II Algorithmes un peu plus avancés
7 Graphes planaires
7.1 Algorithme de reconnaissance
8 Cycles euleriens et hamiltoniens
8.1 Graphes eulériens
8.2 Problème du postier chinois
8.3 Graphes hamiltoniens
8.3.1 Problème du voyageur de commerce
9 Coloration. Stable de cardinal maximum. Clique de cardinal maximum
9.1 Relations entre nombre de clique, nombre de stabilité et nombre de clique
9.2 Heuristiques
9.2.1 Stable maximnal et clique maximale
9.2.2 Coloration gloutonne