Question posée à l'examen écrit du 13 octobre 1997
En s'inspirant de la description de graphes non-orientés en termes de type abstrait vue au cours, nous allons supposer que les types "Graphe" et "SerieDeSommets" ont été définis, sans que vous ne connaissiez les détails de ces structures. Nous allons aussi supposer que les primitives suivantes sont à votre disposition:
function Index(NomSommet: string; LeGraphe: Graphe): integer;
{ retourne un numero compris entre 1 et MaxNbSommets }
function NomSommet(IndexSommet: integer; LeGraphe: Graphe)
:string;
{ retourne le nom du sommet dont l'index est fourni }
function NombreDeSommets(LeGraphe: Graphe): integer;
{retourne le nombre de sommets effectifs composant le graphe}
function SommetsVoisins(IndexSommet: integer;
LeGraphe: Graphe): SerieDeSommets;
{ retourne une structure permettant de retrouver l'index des
voisins immédiats }
function PremierSommet(var UneSerie: SerieDeSommets): integer;
{ extrait le premier des sommets de la série et retourne son
index }
function SommetSuivant(var UneSerie: SerieDeSommets): integer;
{ extrait le prochain sommet de la serie & retourne son index}
function FinDeSerie(UneSerie: SerieDeSommets): boolean;
{ vrai s'il n'y a plus de sommet suivant dans la serie }
En utilisant ces primitives, tout en ignorant de quelle façon la structure de graphe est implantée, écrivez une procédure de parcours en profondeur qui imprime les noms des sommets du graphe fourni en paramêtre:
procedure DFS(LeGraphe: Graphe);
Site Hosting: Bronco