Parcours de graphes à l'aide d'une pile

7.3 Parcours de graphes à l'aide d'une pile

7.3.1 Parcours de labyrinthe

On se propose dans cette section de parcourir un labyrinthe que l'on aura préalablement représenté par un tableau. L'algorithme de parcours repose sur l'utilisation d'une pile.

Construction et affichage de labyrinthe

Les labyrinthes que nous allons utiliser sont des labyrinthes rectangulaires, composés de cases franchissables ou infranchissables. Les cases du bord seront toujours infranchissables sauf en haut à gauche (case de coordonnées (0,1)) et en bas à droite : ce seront les cases de départ et d'arrivée de notre labyrinthe.

Exercice 7.9 --- Affichage de labyrinthe.

Écrivez une fonction qui dessine le labyrinthe en mode texte. Pour ce faire, on définit quelques macros.

#define FERME  0
#define OUVERT 1

Vous pouvez tester cette fonction à l'aide de l'exemple suivant :

#define LONGUEUR 5
#define LARGEUR 6

char petitlab[LONGUEUR][LARGEUR] = 
  {{FERME, OUVERT, FERME, FERME, FERME, FERME},
   {FERME, OUVERT, OUVERT, OUVERT, OUVERT, FERME},
   {FERME, OUVERT, FERME, FERME, FERME, FERME},
   {FERME, OUVERT, OUVERT, OUVERT, OUVERT, FERME},
   {FERME,  FERME, FERME, FERME, OUVERT, FERME}} ;

L'affichage devra correspondre à :

XXXXX
    X
X X X
X X X
X X  
XXXXX

Dans la suite, on convient que la longueur sera de 70 colonnes et la largeur de 30 colonnes. De plus, ce labyrinthe sera représenté par une variable globale.

Exercice 7.10 --- Création du labyrinthe.

Écrivez une fonction qui prend en entrée la probabilité qu'une case soit franchissable et affecte aléatoirement notre labyrinthe de taille longueur×largeur. On rappelle que la fonction rand permet d'obtenir un entier aléatoire.

Cette fonction devra proposer des labyrinthes à l'utilisateur jusqu'à ce que celui-ci accepte l'un d'entre eux (n'oubliez pas de changer la graine de votre générateur d'entiers aléatoires avec la fonction srand()).

Remarquez que cette dernière fonctionnalité permet de choisir un labyrinthe qui ne soit pas trivial à résoudre.

Une pile de pas

Pour parcourir le labyrinthe, nous allons utiliser une pile de pas. Un pas correspond à 4 coordonnées : les deux coordonnées x et y du point de départ du pas et les coordonnées z et t de son point d'arrivée. La pile contiendra les pas élémentaires entre deux cases contigües à explorer ; les coordonnées de départ nous permettrons d'afficher aisément les pas.

Exercice 7.11 --- Structure de la pile.

Implantez une pile globale à l'aide d'un tableau et écrivez les fonctions classiques de manipulations de pile (empiler, dépiler, etc.).

Algorithme de parcours de labyrinthe

Pour parcourir notre labyrinthe, nous allons utiliser une variable globale représentant notre pile et qui contiendra les pas à explorer. Au début du parcours, elle ne contient que le seul pas allant de (0,1) à (1,1).

Tant que notre pile n'est pas vide, on retire le pas de tête. S'il est possible, on réaffiche le labyrinthe en prenant soin de marquer d'un signe les cases déjà visitées pour ne pas boucler. Puis on ajoute à la pile tous les pas possibles (pour lesquels la case d'arrivée est franchissable) à partir du point d'arrivée du pas considéré. Par convention, on ne se déplace pas en diagonale.

Il suffit d'itérer ce qui précède pour sortir du labyrinthe.

Exercice 7.12 --- Implantation de l'algorithme de parcours.

Implantez une fonction parcourir qui parcourt le labyrinthe selon la méthode décrite plus haut. Attention, tous les labyrinthes n'ont pas forcément une sortie !

Remarque.

Notez que le parcours ainsi obtenu n'est en rien optimal. Pour ce faire, il nous faudrait utiliser non pas une pile mais une file. L'étude de cette structure de donnée nécessite l'introduction de structure auto-référencée et dépasse le cadre de cette section (cf. 8).

7.3.2 Jeu de la lettre qui saute

Le but du jeu est de passer d'un mot à un autre par une suite de mots tels qu'un mot et le suivant ne diffèrent que d'une lettre. Par exemple, on peut passer de lion à peur par la suite de mots :

lion -> pion -> paon -> pain -> paix -> poix -> poux -> pour -> peur

Le jeu consiste à se donner deux mots et à voir s'il est possible de passer de l'un à l'autre en respectant les règles.

Nous allons modéliser ce jeu par un graphe : deux mots sont reliés s'il ne différent que d'une lettre. Une suite de mot telle que ci-dessus est donc un chemin dans le graphe. L'ensemble des mots auxquels peut mener un mot constitue une composante connexe. On peut visualiser ces définitions comme suit :

On appellera successeurs d'un mot les mots qui ne différent que d'une lettre de ce mot. Par exemple, les successeurs de lion sont pion et lien, ceux de lien sont rien, bien, sien, lieu, lier, lied, lion, tien et mien.

Pour jouer, on se propose d'utiliser le dictionnaire des mots de quatres lettres que nous avons déjà utilisé pour nous exercer aux tris :

#define taille_dico 979

/* Un dictionnaire de mots de quatre lettres */
char *dico[taille_dico] = { "drap", "nuee", "agit", "mais", "krak", "eric", 
     "aaai", "agir", "drop", "dome", "buis", "rode", "puce", "roda", "drue",
     "buse", "bure", "rode", "haie", "hais", "hait", "puer", "hall", "role",
     "halo", "haro", "puis", "hase", "decu", "pull", "vais", "puma", "haut",
     "valu", "vain", "vase", "alea", "vamp", "thon", "vaux", "vaut", "afin",
     "fier", "fief", "mica", "fiel", "thym", "fini", "midi", "epie", "meat",
     "mien", "fisc", "miel", "film", "mike", "feru", "tige", "mise", "epia",
     "tele", "fevr", "tien", "miss", "mile", "tint", "aout", "fetu", "tilt",
     "mita", "tenu", "mite", "agio", "agir", "agit", "mite", "fele", "ogre",
     "fela", "fele", "meme", "pres", "pref", "aere", "tete", "pret", "tetu",
     "hele", "hote", "here", "foin", "mode", "font", "foot", "moka", "fond",
     "fora", "fort", "toge", "todd", "mont", "mord", "mors", "fore", "mort",
     "four", "toit", "tond", "moto", "tors", "tort", "moue", "moud", "aout",
     "yvan", "tome", "tord", "mous", "yves", "tous", "toux", "flan", "tour",
     "tout", "oeil", "veau", "utah", "utah", "flou", "flot", "heur", "vend",
     "venu", "vent", "velu", "oeuf", "vers", "vert", "flux", "veto", "veuf",
     "veut", "veux", "hale", "hale", "etal", "etai", "etat", "etau", "hata",
     "hate", "ores", "have", "buee", "hate", "jusa", "hair", "etui", "aire",
     "frac", "frai", "fret", "trie", "cade", "tram", "fris", "frit", "froc",
     "cage", "cadi", "trac", "duel", "jade", "cake", "tria", "cane", "dune",
     "camp", "trio", "dura", "cafe", "troc", "mole", "came", "trot", "jais",
     "rude", "trop", "trou", "aine", "ruer", "janv", "tole", "jase", "jars",
     "jasa", "dure", "truc", "java", "jazz", "jase", "rush", "tsar", "epee",
     "clot", "aile", "aigu", "aide", "aine", "hele", "hier", "aile", "vice",
     "vecu", "aise", "aera", "hela", "vint", "viol", "aise", "visa", "vise",
     "aere", "hetu", "vive", "vite", "velo", "ange", "once", "vise", "anis",
     "anon", "onde", "anse", "ansi", "anus", "onze", "cene", "vetu", "onyx",
     "cepe", "hors", "home", "ceci", "houx", "vois", "voir", "voit", "voeu",
     "voix", "cout", "houe", "voie", "volt", "vont", "jean", "coit", "cens",
     "alfa", "cent", "allo", "vote", "vous", "cerf", "cern", "aloi", "jerk",
     "ceux", "jeun", "alto", "vlsi", "amas", "amen", "amer", "ames", "omet",
     "omis", "omit", "arcs", "caid", "oral", "orge", "vrac", "vrai", "fuel",
     "ardu", "ardt", "fuit", "chas", "char", "orme", "aria", "chef", "hote",
     "laid", "sage", "lait", "land", "muni", "tuer", "mule", "lama", "lard",
     "ores", "laps", "turc", "turf", "lame", "fuir", "chai", "chah", "sapa",
     "chat", "mure", "muer", "muet", "full", "sake", "cher", "chez", "saga",
     "saur", "oser", "chic", "tuez", "lame", "choc", "chou", "mura", "musc",
     "muse", "sain", "sais", "sait", "sana", "sang", "sans", "sali", "apex",
     "fute", "sari", "sape", "chut", "sauf", "saut", "sape", "osez", "saxo",
     "jill", "ciel", "cinq", "cime", "opus", "apre", "opte", "apte", "opta",
     "opte", "aval", "cola", "john", "lese", "jonc", "joli", "cote", "coco",
     "tres", "coke", "coin", "conf", "seau", "colt", "seme", "coma", "avec",
     "aveu", "avez", "corp", "joie", "cosy", "clip", "avis", "seme", "lest",
     "sein", "coud", "coup", "cour", "sens", "sent", "self", "sera", "serf",
     "seve", "sers", "zele", "sert", "cote", "type", "joug", "typo", "jour",
     "auto", "ubac", "ovni", "owen", "legs", "clam", "clan", "clef", "aube",
     "lent", "clin", "soul", "clos", "clou", "sema", "leur", "sept", "club",
     "seul", "type", "sexe", "sexy", "skie", "ucla", "crue", "atre", "gain",
     "huit", "gang", "hune", "gala", "gale", "naja", "html", "cote", "nain",
     "cran", "shah", "laic", "aube", "cric", "crin", "cris", "croc", "auge",
     "skia", "cone", "audy", "aune", "huer", "crut", "aura", "cote", "gant",
     "oued", "lice", "auto", "gars", "nais", "lift", "lien", "ours", "nasa",
     "lion", "sied", "nazi", "lira", "lire", "zebu", "lise", "lisp", "show",
     "zele", "lesa", "zinc", "zero", "azur", "lied", "lier", "lieu", "lino",
     "sien", "snob", "silo", "sire", "site", "lese", "oree", "gene", "sofa",
     "loin", "loir", "long", "lors", "soif", "axer", "soir", "ieee", "ayez",
     "zone", "sole", "soli", "sors", "loup", "zona", "zone", "zoom", "gout",
     "noel", "souk", "soya", "mans", "gere", "soda", "soja", "neuf", "soin",
     "soit", "ieee", "sono", "sont", "ibid", "ibis", "geai", "solo", "slip",
     "loto", "sort", "slow", "gens", "nerf", "elle", "nait", "naif", "ouie",
     "ouir", "cube", "erra", "bail", "bain", "cuir", "gata", "gate", "judo",
     "pack", "jube", "gate", "page", "juin", "pane", "quel", "jury", "jupe",
     "paon", "cure", "pars", "paru", "baba", "cuba", "paul", "gite", "watt",
     "erre", "apic", "cube", "cuis", "cuit", "banc", "bang", "jude", "quai",
     "cure", "basa", "base", "juif", "erre", "cuti", "baud", "baux", "pain",
     "pair", "paix", "quoi", "pale", "base", "jute", "parc", "pari", "part",
     "papa", "pape", "neon", "pays", "esse", "gere", "spie", "spot", "neve",
     "gena", "nier", "girl", "unir", "unit", "unix", "gera", "noce", "gond",
     "hifi", "gene", "pere", "noir", "noix", "gnon", "nord", "gene", "nous",
     "ieee", "peau", "idem", "ides", "pend", "goal", "perd", "perl", "pers",
     "peur", "peut", "ebat", "gong", "golf", "pese", "pese", "beau", "pame",
     "glas", "pale", "pama", "pame", "ilot", "pate", "pesa", "stem", "echo",
     "echu", "pate", "ecot", "swap", "ecru", "gras", "bale", "stuc", "grog",
     "gros", "urge", "bati", "daim", "luge", "atil", "race", "dame", "urne",
     "etes", "rame", "luit", "suez", "luxe", "kart", "etre", "star", "raid",
     "suce", "suif", "rail", "suis", "suit", "suiv", "rang", "luth", "rare",
     "surf", "phil", "stop", "yard", "grec", "greg", "user", "gril", "gris",
     "beat", "dada", "dais", "lune", "grue", "kaki", "pied", "dard", "pieu",
     "daze", "lune", "urge", "yack", "suer", "lump", "race", "suie", "rama",
     "rame", "rami", "rapt", "luxa", "luxe", "rave", "rata", "rate", "indu",
     "usez", "bien", "pneu", "beer", "bebe", "bile", "bise", "pige", "exil",
     "pion", "egal", "pire", "pipe", "inca", "pise", "boxe", "idee", "inne",
     "ions", "pois", "poix", "inox", "pool", "poli", "dela", "insu", "port",
     "beta", "bete", "pope", "edam", "pene", "pouf", "pour", "poux", "bock",
     "edit", "kent", "rein", "bois", "boit", "bond", "boni", "plan", "iode",
     "boom", "bord", "iode", "bouc", "boue", "boul", "bous", "bout", "poil",
     "pond", "pont", "boxa", "boxe", "polo", "iota", "porc", "pore", "yeux",
     "plut", "dent", "demi", "bleu", "blet", "rene", "lynx", "bloc", "lyre",
     "lyse", "deux", "rala", "rale", "rend", "plat", "utah", "plot", "elle",
     "suca", "bref", "irai", "imbu", "rale", "irez", "iris", "fame", "irmx",
     "guet", "pris", "prit", "prix", "imsl", "tact", "nuit", "malt", "mare",
     "mari", "taie", "tain", "bras", "tank", "taon", "talc", "ntsc", "maux",
     "bric", "brie", "item", "brio", "brin", "bris", "broc", "brou", "taux",
     "face", "unir", "fade", "fane", "irmx", "mach", "brun", "brut", "rhum",
     "deja", "faim", "mage", "fais", "fait", "fana", "fane", "unir", "faon",
     "uucp", "pole", "fard", "fart", "mail", "main", "dine", "khan", "marc",
     "mark", "mars", "isba", "faut", "dina", "faux", "dine", "tais", "tait",
     "tant", "dery", "rien", "dime", "riez", "kilt", "math", "ture", "tard",
     "reel", "tapi", "ring", "maya", "rira", "rire", "tare", "taxi", "issu",
     "dick", "rite", "defi", "dieu", "deni", "dira", "dire", "dise", "rime",
     "king", "kilo", "dito", "reer", "kiwi", "rima", "kepi", "rime", "uree",
     "dois", "donc", "rock", "rixe", "dors", "dose", "kola", "dota", "acte",
     "rond", "roll", "dose", "gres", "ivre", "rene", "dock", "fend", "roux",
     "teck", "dodu", "mens", "ment", "deca", "doit", "abat", "feue", "dont",
     "recu", "tend", "feve", "tenu", "dort", "dosa", "abbe", "meus", "meut",
     "test", "doux", "yoga", "abus", "abri", "dote", "doue", "rose", "abus",
     "elan", "roue", "mout", "fera", "rose", "ocre", "roue", "menu", "elit",
     "elis", "elle", "obus", "mess", "male", "elue", "elut", "acre", "acre",
     "acte", "emet", "emit", "emir", "emis", "emoi", "item", "oter", "emue",
     "emut" };

Représentation d'un graphe

La représentation la plus directe d'un graphe à n sommets est celle par matrice d'incidence : on utilise un tableau M de taille n× n où M[i][j] est égal à 1 s'il existe une arête entre le sommet i et le sommet j, et à 0 sinon.

Dans notre cas, les sommets correspondent à des mots. On décide de représenter chaque mot par son indice dans le dictionnaire dico. Il est donc judicieux de trier ce dictionnaire afin de pouvoir déterminer par une recherche dichotomique l'indice associé à un mot.

Exercice 7.13 --- Construction de la matrice d'incidence.

Construisez une fonction qui prenne en entrée une matrice d'incidence. Cette fonction devra construire la matrice d'incidence associée au dictionnaire défini globalement et la stocker dans la matrice d'incidence passée en argument.

Pour ce faire, on peut construire une fonction qui prend en arguments deux chaînes de caractères et qui retourne 1 s'il s'agit de successeurs et 0 sinon.

Parcours en profondeur de notre graphe

Nous pouvons maintenant aborder le jeu proprement dit. Deux mots étant donnés, il nous faut parcourir notre graphe à partir d'un sommet (premier mot) jusqu'à ce que :

soit on rencontre le second mot (un sommet donné) ;
soit on termine le parcours sans faire cette rencontre et on démontre ainsi qu'il n'est pas possible de passer du premier mot au second en respectant les règles.

Cette démarche nous rappelle celle utilisée lors du parcours de labyrinthe. Nous pouvons donc utiliser le même type de solution.

Exercice 7.14 --- Parcours du graphe des mots.

À l'aide d'une pile, implanter une fonction qui prend en argument une matrice d'incidence et deux chaînes de caractères ; cette fonction retourne 1 s'il est possible de passer du premier au second en respectant les règles de notre jeu.

Pour ce faire, il nous faut convertir les mots en les indices associés qui vont représenter les sommets. Cette opération nécessite une fonction de recherche dichotomique.

Remarques :

dans cet exercice, nous n'avons pas donné le chemin existant entre deux mots. De plus, on pourrait demander de fournir toutes les composantes connexes de ce graphe.

Ce genre d'étude est facilement réalisable du moment que l'on dispose de listes chaînés ou d'arbres. Ces deux structures de données n'ont pas été abordée jusqu'à présent.

Pour tout commentaire : Alexandre Sedoglavic.