TP2 : parcours, arbres couvrants ...

Le but de ce TP est de continuer sur la lancée du TP1 (TP1 : représentation des graphes, parcours en largeur...) en continuant à utiliser les fichiers données la semaine dernière.

Les fonctions à écrire sont les suivantes :

• diametre pour calculer le diamètre d'un graphe (Diamètre d'un graphe),
• composantesFortemenentConnexes pour calculer les composantes fortement connexes d'un graphe orienté (Composantes fortement connexes),
• tri_topologique pour linéariser un graphe orienté sans cycle (Le tri topologique),
• prim pour calculer un arbre couvrant de poids minimal (Algorithme de Prim).

L'archive contenant les fichiers necessaires pour le TP se trouve ici : http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info505/tp.tgz .

Diamètre d'un graphe

Pour commencer, finissez le TP1 en programmant une fonction efficace pour calculer le diamètre d'un graphe : Diamètre d'un graphe.

Composantes fortement connexes

Le parcours en profondeur simple

Avant de vous lancer dans la recherche de composantes fortement connexes, je vous conseille de programmer la version simple du parcours en profondeur. Pour apporter un peu de changement, faites le parcours en n'utilisant que deux tableaux :

• le tableau debut, initialisé à -1 pour tous les sommets,
• le tableau fin, initialisé à -1 pour tous les sommets.

Ces deux tableaux seront passés en paramètres à la fonction parcours_profondeur, et vous écrirez une fonction int foret(int debut[], int fin[]); qui calculera la foret couvrante à partir des 2 tableaux debut et fin.

Note:

Pour pouvoir définir une fonction récursive en C, il ne faut pas oublier de la déclarer pour que le compilateur soit content :

• vous pouvez soit mettre le prototype de la fonction avant sa définition :

  int fib (int n);
  int fib (int n) {
    if (n<2) return n;
    else return(fib(n-1)+fib(n-2));
  }
  

• ou bien vous mettez le prototype de votre fonction dans un fichier d'entêtes approprié, que vous incluez dans votre source.

Composantes fortement connexes

En utilisant les fonctions du TP1, programmez maintenant l'algorithme vu en cours pour calculer les composantes fortement connexe d'un graphe orienté. Quelques points importants :

• découper votre programme en fonction et procédures,
• pensez à la complexité globale de votre fonction,
• commentez votre programme.

Je dois pouvoir reconnaître l'algo dans votre code source au premier coup d'oeil. Si vous deviez de l'algo donné en cours, justifiez les changements.

Le tri topologique

Mathématiquement parlant, le tri topologique consiste à linéariser un ordre partiel. Plus concrètement, le tri topologique permet d'ordonnancer un ensemble de tache en respectant des contrainte de précédente. Pour que cela soit possible, il ne faut pas que les contraintes soient cyclique, mais quand ce n'est pas le cas, on peut toujours trouver un ordre séquentiel qui respecte les contraintes.

L'algorithme est le suivant :

tri_topologique(G) {
  liste := NULL               // une liste chaînée
  parcours_profondeur_bis(G)  // comme parcours_profondeur[], mais
                              // chaque fois qu'un sommet devient
                              // "examiné", on le place en tête de
                              // "liste"
renvoie(liste)
}

Le prototype de la fonction que vous devez programmer est le suivant :

int*triTopologique (const GrapheListe G);

et des commentaires concernant son utilisation sont présents dans le fichier graphes.h.

Vous aurez probablement besoin de définir des fonctions auxiliaires...

Bonus

Vous aurez un point bonus si votre tri topologique vérifie en même temps si le graphe est sans cycle et renvoie le pointeur NULL dans ce cas.

Essayez de faire ça intelligemment...

Algorithme de Prim

Programmez l'algorithme de Prim vu en cours. Encore une fois, commentez votre code et justifiez les choix que vous faites...

Vous aurez probablement besoin d'utiliser une variante de cette fonction lors du TP3, alors essayez de la faire.