Arbres et graphes

Comprendre la structure avant l’algorithme

Un graphe sert à représenter des objets et leurs relations. Les objets sont des sommets. Les relations sont des arêtes si elles n’ont pas de sens, ou des arcs si elles sont orientées.

Un arbre est un graphe particulier. Il est connexe et ne contient pas de cycle. Cela signifie que tout sommet reste atteignable depuis les autres, et qu’il n’existe pas de boucle permettant de revenir au point de départ par un autre chemin. Dans un arbre, entre deux sommets distincts, il existe un unique chemin.

En NSI, on ne manipule pas seulement ces structures comme des dessins. On les code. Le bon réflexe consiste donc à passer vite de la représentation visuelle à une représentation en mémoire.

Notion	Définition utile	Point à surveiller
Graphe non orienté	Les relations n’ont pas de sens imposé.	Si A est relié à B, alors B est relié à A.
Graphe orienté	Les relations ont un sens.	Un arc de A vers B ne donne pas forcément un arc de B vers A.
Graphe pondéré	Chaque arête ou arc porte un coût.	Le plus court chemin dépend des poids, pas du nombre d’arêtes.
Arbre	Graphe connexe sans cycle.	Un seul chemin entre deux sommets.
Arbre enraciné	Arbre avec un sommet choisi comme racine.	Les relations parent, enfant et feuille dépendent de la racine.

Les mots connexe, cycle, chemin, distance et degré reviennent souvent. Le degré d’un sommet compte ses voisins dans un graphe non orienté. Dans un graphe orienté, on distingue les arcs entrants et les arcs sortants.

Représenter un graphe en programme

Deux représentations dominent au lycée : la matrice d’adjacence et la liste d’adjacence. Elles ne répondent pas au même besoin.

Matrice d’adjacence

Une matrice d’adjacence associe une ligne et une colonne à chaque sommet. La case indique si les deux sommets sont reliés. Pour un graphe pondéré, la case peut contenir le poids de l’arête ou de l’arc.

Exemple avec les sommets A, B, C, D. On a les arêtes A B, A C, B D et C D. Une matrice possible est :

	A	B	C	D
A	0	1	1	0
B	1	0	0	1
C	1	0	0	1
D	0	1	1	0

La matrice est symétrique, car le graphe est non orienté. Dans un graphe orienté, cette symétrie peut disparaître.

Liste d’adjacence

Une liste d’adjacence associe à chaque sommet la liste de ses voisins. Pour le même graphe, on peut écrire :

A : B, C

B : A, D

C : A, D

D : B, C

Cette représentation est souvent plus naturelle pour parcourir un graphe. Elle évite de consulter beaucoup de cases inutiles quand le graphe contient peu d’arêtes par rapport au nombre de sommets.

• Tester l’existence d’une arête : la matrice donne une réponse directe.
• Parcourir les voisins d’un sommet : la liste d’adjacence est très lisible.
• Graphe orienté : ne pas ajouter automatiquement le voisin dans les deux sens.
• Graphe pondéré : stocker aussi le poids, par exemple avec des couples comme (voisin, cout).

Parcourir un graphe sans se perdre

Un parcours explore les sommets à partir d’un sommet de départ. Il faut toujours mémoriser les sommets déjà visités. Sinon, un cycle peut provoquer une boucle sans fin.

Parcours en profondeur

Le parcours en profondeur suit un chemin le plus loin possible, puis revient en arrière. Il se programme naturellement avec une fonction récursive ou avec une pile.

Schéma d’idée :

visiter(s)

marquer s

pour chaque voisin v de s non marque, visiter(v)

Ce parcours sert à détecter une composante connexe, chercher un chemin, explorer un arbre ou vérifier une propriété globale.

Parcours en largeur

Le parcours en largeur explore d’abord les voisins directs, puis les voisins des voisins. Il utilise une file. Dans un graphe non pondéré, il permet d’obtenir les distances minimales en nombre d’arêtes depuis le sommet de départ.

Principe :

1. Placer le sommet de départ dans une file.
2. Le marquer comme visité.
3. Extraire le premier sommet de la file.
4. Ajouter ses voisins non visités à la fin de la file.
5. Recommencer jusqu’à ce que la file soit vide.

Exemple pas à pas

On reprend le graphe non orienté suivant :

A : B, C

B : A, D, E

C : A, F

D : B

E : B, F

F : C, E

On effectue un parcours en largeur depuis A, en lisant les voisins dans l’ordre alphabétique.

1. Départ : file A. Sommets visités : A. Distance de A à A : 0.
2. On retire A. On ajoute B et C. File B, C. Distances : B vaut 1, C vaut 1.
3. On retire B. Ses voisins sont A, D, E. A est déjà visité. On ajoute D et E. File C, D, E. Distances : D vaut 2, E vaut 2.
4. On retire C. Ses voisins sont A et F. A est déjà visité. On ajoute F. File D, E, F. Distance : F vaut 2.
5. On retire D. Son seul voisin B est déjà visité. File E, F.
6. On retire E. Ses voisins B et F sont déjà visités. File F.
7. On retire F. Ses voisins C et E sont déjà visités. File vide.

L’ordre de visite est donc A, B, C, D, E, F. Les distances depuis A sont : A vaut 0, B vaut 1, C vaut 1, D vaut 2, E vaut 2, F vaut 2. On voit que F est atteint en deux arêtes par le chemin A C F. Le chemin A B E F existe aussi, mais il contient trois arêtes, donc il n’est pas minimal.

Arbres : racine, récursion et parcours

Un arbre peut être vu comme un graphe, mais on l’étudie souvent avec une racine. À partir d’elle, on parle de parent, d’enfant, de frère, de profondeur et de feuille.

Une feuille est un sommet sans enfant. La profondeur d’un sommet correspond au nombre d’arêtes entre la racine et ce sommet. La hauteur d’un arbre dépend du plus long chemin de la racine vers une feuille.

Les arbres binaires occupent une place particulière. Chaque nœud possède au plus deux enfants : un enfant gauche et un enfant droit. Cette structure convient à de nombreux traitements récursifs, car chaque sous-arbre se traite comme un arbre plus petit.

Parcours d’un arbre binaire

Trois parcours sont à connaître. Ils ne donnent pas le même ordre.

• Parcours préfixe : racine, sous-arbre gauche, sous-arbre droit.
• Parcours infixe : sous-arbre gauche, racine, sous-arbre droit.
• Parcours suffixe : sous-arbre gauche, sous-arbre droit, racine.

Dans un arbre binaire de recherche, le parcours infixe donne les valeurs dans l’ordre croissant, si la règle de placement est respectée : les valeurs plus petites sont à gauche, les valeurs plus grandes sont à droite.

Exemple avec un arbre binaire de recherche

On insère les valeurs 8, 3, 10, 1, 6, 14, 4, 7, 13 dans cet ordre.

1. 8 devient la racine.
2. 3 est plus petit que 8, il va à gauche.
3. 10 est plus grand que 8, il va à droite.
4. 1 est plus petit que 8, puis plus petit que 3, il va à gauche de 3.
5. 6 est plus petit que 8, puis plus grand que 3, il va à droite de 3.
6. 14 est plus grand que 8, puis plus grand que 10, il va à droite de 10.
7. 4 est plus petit que 8, plus grand que 3, puis plus petit que 6, il va à gauche de 6.
8. 7 est plus petit que 8, plus grand que 3, puis plus grand que 6, il va à droite de 6.
9. 13 est plus grand que 8, plus grand que 10, puis plus petit que 14, il va à gauche de 14.

Le parcours infixe donne alors 1, 3, 4, 6, 7, 8, 10, 13, 14. On obtient bien les valeurs triées. Le parcours préfixe donne 8, 3, 1, 6, 4, 7, 10, 14, 13. Le parcours suffixe donne 1, 4, 7, 6, 3, 13, 14, 10, 8.

Plus courts chemins et arbres couvrants

Dans un graphe pondéré, la question n’est plus seulement : peut-on aller d’un sommet à un autre ? Elle devient : quel chemin minimise le coût total ? Le coût d’un chemin est la somme des poids des arêtes ou des arcs empruntés.

Pour raisonner correctement, distinguer deux cas. Si le graphe n’est pas pondéré, un parcours en largeur donne des distances minimales en nombre d’arêtes. Si le graphe est pondéré avec des poids positifs, on utilise un algorithme adapté, souvent fondé sur des mises à jour de distances provisoires.

Exemple simple. On cherche le plus court chemin de A vers D dans un graphe orienté pondéré :

A vers B : 2

A vers C : 5

B vers C : 1

B vers D : 4

C vers D : 2

On part de A. Distance de A : 0. Distances provisoires : B vaut 2, C vaut 5, D est inconnue. On choisit B, car 2 est la plus petite distance provisoire. Depuis B, on peut améliorer C : passer par A puis B puis C coûte 0 + 2 + 1, donc 3. C passe de 5 à 3. On peut aussi atteindre D par B avec un coût 0 + 2 + 4, donc 6. D vaut 6.

On choisit ensuite C, distance 3. Depuis C, atteindre D coûte 0 + 2 + 1 + 2, donc 5. D passe de 6 à 5. On choisit enfin D. Le plus court chemin trouvé est A B C D, de coût 5.

Un arbre couvrant d’un graphe non orienté connexe relie tous les sommets sans cycle. Il garde juste assez d’arêtes pour conserver la connexité. Dans un graphe pondéré, on peut chercher un arbre couvrant de poids minimal. L’idée générale consiste à sélectionner des arêtes utiles sans créer de cycle, jusqu’à relier tous les sommets.

Méthode à appliquer le jour de l’évaluation

1. Identifier la structure. Graphe ou arbre ? Orienté ou non ? Pondéré ou non ? Enraciné ou non ? Cette étape détermine tout le reste.
2. Traduire le dessin. Écrire la liste d’adjacence ou la matrice. Vérifier les deux sens pour un graphe non orienté. Ne pas inventer de symétrie dans un graphe orienté.
3. Marquer les sommets visités. Dans tout parcours, prévoir un ensemble de sommets déjà vus. C’est la protection contre les cycles et les répétitions.
4. Choisir le bon parcours. Profondeur pour explorer une branche, tester une connexité ou travailler récursivement. Largeur pour obtenir une distance minimale en nombre d’arêtes dans un graphe non pondéré.
5. Suivre la structure de données. Pour la profondeur, penser pile ou récursion. Pour la largeur, penser file. Écrire l’état de cette structure à chaque étape si l’exercice demande un déroulé.
6. Pour un arbre binaire, nommer clairement la racine, les sous-arbres, les feuilles. Pour un parcours, appliquer toujours le même ordre : préfixe, infixe ou suffixe.
7. Pour un plus court chemin pondéré, additionner les poids. Comparer les coûts provisoires. Mettre à jour seulement si le nouveau coût est meilleur.
8. Relire avec les propriétés. Un arbre ne contient pas de cycle. Un graphe non orienté donne des relations réciproques. Un parcours en largeur ne remplace pas un algorithme de plus court chemin pondéré.

Signature : Hugo Arbonnier