Implémentation et parcours de graphe en OcamL

Algorithme

Lorsque l’on détermine les voisins d’un sommet. On sait que l’on doit tous les visiter. Une idée serait donc de mettre dans un ensemble les sommets qu’il reste à visiter. Nous n’allons pas expliciter l’implémentation d’un tel ensemble (qui correspondra à une file ou à une pile, mais nous généralisons le procédé dans un premier temps), on supposera qu’il dispose des opérations suivantes :
• [] : représente l’ensemble vide • ensembleChoisir (Ensemble) -> element : retourne un élément de l’ensemble • ensembleRetirer (Ensemble) -> Ensemble : retire l’élément que l’on obtient avec ensembleChoisir
Implémentation et parcours de graphe en OcamL par Humbert Florent (millie)
• ensembleUnion(Ensemble 1, Ensemble 2) -> Ensemble : détermine la réunion des deux ensembles (on peut supposer qu’il existe des doublons) • element appartient Ensemble -> Booléen est vrai si l’élément appartient à l’ensemble et faux sinon
À un moment du parcours, on suppose que l’on dispose des 2 ensembles suivants :
• avisiter : l’ensemble des sommets qu’il reste à visiter • aetevisite : l’ensemble des sommets qui ont déjà été visité
L’algorithme peut s’écrire comme suit :

fonction Parcours g avisiter aetevisite= Si avisiter = [] alors /*Si il ne reste rien à visiter, on a fini*/ fin; Sinon sommetcourant = ensembleChoisir(avisiter) /*sommet que l’on traite*/ resteavisiter = ensembleRetirer(avisiter) Si sommetcourant appartient à aetevisite alors /*Si l’élément a déjà été visité*/ Parcours g aetevisite resteavisiter /*on visite les sommets suivants*/ Sinon /* on ajoute au élément à visiter les voisins du sommet courant, et on ajoute le sommetcourant au élément qui ont été visité*/ Parcours g ensembleUnion(resteavisiter, voisin(g, sommetcourant)) ensembleUnion(aetevisite, sommetcourant)

Explicitation du type Ensemble

Nous allons chercher à expliciter le type ensemble, cela nous permettra de définir l’implémentation du graphe afin d’optimiser le parcours.
Il faut noter que même si l’ensemble admet des doublons, l’algorithme est bon. Cela nous permet ainsi d’envisager un type liste pour l’ensemble avisiter. L’opération ensembleChoisir consistera juste à prendre le premier élément de la liste. et l’opération ensembleRetirer consistera à prendre la queue de la liste.
Ce qui devient intéressant, c’est le choix d’implémentation de l’opération ensembleUnion. Si l’on choisit d’ajouter les éléments à la queue de la liste, l’algorithme devient un parcours en largeur et si l’on choisit d’ajouter les éléments à la tête de la liste, cela devient un parcours en profondeur.
Ainsi, dans le cas du parcours en largeur, comme on ajoute les éléments à la queue de la liste, cela revient à utiliser comme implémentation du type Ensemble une file. Dans le parcours en profondeur, cela revient à utiliser une pile.