11. Structures récursives non linéaires: les graphes orientés

Les graphes orientés sont des graphes dont les arcs ne peuvent être parcourus que dans un seul sens. Ceci ajoute une difficulté pour vérifier certaines propriétés du graphe. Pour mieux comprendre le concept, on peut faire les analogies suivantes :

• Déplacement dans une ville où il y a de nombreux sens interdits.

• Déplacement à l'intérieur d'un pays où les lignes aériennes assument rarement l'aller-retour entre deux villes.

Le sens associé à un arc peut aussi traduire une relation de précédence dans le modèle de l'application (relation d'ordre partielle). Par exemple, pour la modélisation d'une chaîne de production :

sommet = tâche à exécuter

arc

= précédence des tâches les unes par rapport aux autres. Un arc de X vers Y signifie que la tâche Y ne peut commencer que quand la tâche X est terminée.

Ainsi, pour la production d'une voiture, on peut avoir les relations de précédence suivantes :

• le pare-brise doit être monté après que le châssis ait été peint.
• l'installation électrique doit être faite après que le châssis ait été peint.

Il peut très bien ne pas y avoir de relation directe entre le montage du pare-brise et l'installation électrique.

Dans ce chapitre, nous examinerons diverses variantes de l'algorithme de parcours en profondeur (DFS) permettant de vérifier les propriétés de connectivité d'un graphe ou d'en sérialiser les sommets.

11.1. Représentation d'un graphe orienté

Table des matières.

Site Hosting: Bronco