Tri topologique inverse

Question posée à l'examen du 7 octobre 1998

En s'inspirant de la description de graphes 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 ExtraitSommet(var UneSerie: SerieDeSommets): integer;
  { extrait un sommets de la série et 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 tri topologique inverse qui imprime les sommets du graphe fourni en paramêtre: 
TriTopologiqueInverse(LeGraphe: Graphe)

Solution

Site Hosting: Bronco