Le TP est à rendre (par email) pour le mercredi 16 décembre à 8h00.
Pour ce TP comme pour les suivants, la pièce la plus importante sera un fichier tp2-nom-prenom.c contenant votre programme. Le seul fait que votre programme fonctionne ne suffit pas pour avoir une bonne note. Les points suivants seront également pris en compte :
Les réponses aux questions posées dans le TP (complexité de vos fonctions par exemple) seront insérées comme commentaires dans votre fichier principal.
Attention : les points suivants ne rapportent rien, mais ne pas les respecter pourra retrancher jusqu'à 10 points sur la note finale :
-Wall -Werror -Wextra -pedantic -std=c99.
Makefile fourni comme pour le TP1. Il suffit de modifier la variable NOM pour prendre en compte votre propre fichier.
L'archive du TP contient le fichier graphes.c. Il contient les définitions des fonctions déclarées dans graphes.h.
Nous avons vu pendant le TD2 l'algorithme du « tri topologique ». Cet algorithme permet de linéariser un graphe orienté sans cycle et fonctionne de la manière suivante : on effectue un parcours en profondeur et on trie les sommets par ordre de « fin[] » décroissant.
Écrivez la fonction triTopologique de prototype
int *triTopologique(GrapheListe G) ;
Les consignes sont les suivantes :
4, 1, 0, 3, 5, 2, alors le résultat sera un tableau T avec T[0]=4, T[1]=1, T[2]=0, T[3]=3, T[4]=5, T[5]=2.
NULL.
Donnez la complexité de votre fonction, en justifiant.
Votre fonction devra être la plus simple possible et n'utilisera pas les listes chaînées comme structure intermédiaire.
(N'oubliez pas de documenter ce que vous faites...)
Calculer les composante connexes dans un graphe non-orienté se fait facilement avec un parcours.
Décrivez un algorithme simple (sans forcement l'écrire) pour calculer les composantes connexes d'un graphe non-orienté. Les consignes sur le résultat de votre fonction sont les mêmes que pour la question suivante...
Une composante fortement connexe dans un graphe orienté est un ensemble maximal de sommets qui vérifie la propriété suivante : « il existe un chemin orienté de n'importe quel sommet vers n'importe quel autre ».
Une manière de calculer les composantes fortement connexe du graphe G est de procéder comme suit :
G
G', le transposé de G
G', __en prenant les sommets par ordre de fin[] décroissant. (L'ordre de fin[] est donné par le parcours de G.)
Programmer la fonction de prototype :
int composantesFortementConnexes(GrapheListe G, int *CC) ;
Sa valeur de retour sera le nombre de composantes fortement connexes du graphe G, et l'argument CC sera un tableau que l'on remplira avec les numéro de composantes fortement connexes : si le sommet s est dans la composante connexe c, alors après l'appel à la fonction on aura CC[s] == c.
Comme pour la question 1, essayer d'avoir un code le plus simple possible et documentez bien ce que vous faites.
Implémentez l'algorithme de Prim pour calculer un arbre couvrant de poids minimal dans un graphe non-orienté :
int prim(GrapheListe G, int *foret) ;
Votre fonction devra renvoyer le poids minimal trouvé et stocker l'arbre en question dans le tableau foret[].
Les fonctions grilleRectPleine() et grilleHexPleine() créent des grilles rectangulaire / hexagonal pleines avec des poids aléatoires. Si on recherche un arbre couvrant de poids minimal, on obtient donc un arbre aléatoire sur la grille, c'est à dire un labyrinthe.
Générez des labyrinthes en écrivant les fonctions labyrintheRect() et grilleHexPleine().
Comparez avec les labyrinthes crées par des parcours en largeur ou des parcours en profondeur, où l'on prend les arêtes par ordre croissant de poids.