Les graphes

Un graphe est constitué par un ensemble d'objets représenté par des sommets reliés entre eux par des liens (les arêtes du graphe).Un graphe permet de représenter le réseau ferroviaire, le réseau internet, un labyrinthe ou certains problèmes de choix de chemins.

Le problème est : un berger possède une chèvre, un loup et un chou lors de cet exemple. Le berger empêche de manger la chèvre et la chèvre empêche de manger. Si le berger est présent, le loup mange la chèvre et la chèvre peut, quant à elle, mange le chou.

Il y a 16 situations possibles. Chaque état sera simplement décrit grâce au personnage présent sur la rive départ.

Liste des états interdits:

• C Cx.

• B Cx.

• B L.

• L C.

État de la rive de départ :

1 : Traversée Berger + Chèvre

2 : Retour du Berger

3 : Traversée Berger + Loup

4 : Retour Berger + Chèvre

5 : Traversée Berger + Choux

6 : Retour Berger

7 : Traversée Berger + Chèvre.

Les intersections sont les sommets du graphe et sont repérées par des lettres. Les couloirs sont les arêtes.

1 - A

2 - AB

3 - ABC ABM

4 - ABCD ABCK ABM

5 - ABCD ABCK ABMN (impasse) ABMZ (solution)

Le parcours en largeur permet de trouver le chemin le plus court pour sortir du labyrinthe.

1 - A

2 - AB

3 - ABC ABM

4 - ABCD ABCK ABM

5 - ABCDE ABCDK ABCK ABM

6 - ABCDEF  ABCDEG ABCK ABM

7 - ABCDEGH  ABCDEGI ABCK ABM

8 - ABCDEGIJ   ABCK ABM

9 - ABCKD ABCKL   ABM

10 - ABMN  ABMZ solution

parcours de profondeur