TP1 : représentation des graphes, parcours en largeur...

Le but de ce premier TP est

de programmer quelques fonctions utilitaires sur les graphes (Représentation et fonctions utilitaires)
de programmer une fonction efficace pour tester si un graphe est biparti (Graphes bipartis)
de programmer une fonction efficace pour calculer le diamètre d'un graphe (Diamètre d'un graphe)

Les fonctions utilitaires que vous n'avez pas besoin de programmer sont dans l'archive http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info505/tp.tgz .

Modalités du TP

Pour chaque groupe, je demande un unique fichier identifiants.c contenant du code C valide. Votre fichier doit compiler si vous utilisez le Makefile (après modification de la variable NOM) et les fichiers complémentaires fournit dans l'archive http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info505/tp.tgz

Votre code doit être autosuffisant, c'est à dire bien commenté, lisible et clair. Utilisez l'indentation correctement et n'abusez pas des espaces.

Les réponses aux questions plus théoriques devront se trouver en commentaire avant les fonctions pertinentes.

Représentation et fonctions utilitaires

Le fichier graphes.h décrit les structures de données choisies pour représenter les graphes. Ce fichier contient également les prototypes des fonctions nécessaires pour la compilation de mon fichier de test, et pour réussir le TP.

Par rapport à ce qui a été dit en cours, on a rajouté un poids pour les arcs du graphes.

Note:: Remarque pour les matrice d'adjacence, j'ai fait le choix de représenter une matrice par un int **M afin de ne pas avoir à s'embêter avec la largeur de la matrice. Suivant les applications que vous envisagez, il pourrait être plus intéressant d'aplatir le tableau en un int *M.

Certaines des fonctions utilitaires sont définies dans le fichier graphes.c : vous n'avez donc pas besoin de les reprogrammer.

Les fonctions que vous devrez programmer sont les suivantes :

afficheGrapheListe, une petite fonction d'affichage en mode texte. Voici par exemple un type d'affichage possible :

Le graphe a 8 sommets :
  0  --(5)-->  2
  0  --(4)-->  1
  1  --(6)-->  2
  2  --(7)-->  3
  3  --(8)-->  4
  4  --(9)-->  5
  5  --(10)-->  6
  6  --(11)-->  7
  7  --(12)-->  0
Le graphe a 9 arcs

listeVersMatrice et matriceVersListe, les deux fonctions de conversion entre la représentation sous forme de liste d'adjacence et sous forme de matrice d'adjacence,
transpose, la fonction qui calcule l'inverse d'un graphe en renversants tous les arcs.

Note:: Une solution alternative pour afficher les graphes seraient de générer une représentation du graphe pour un visualisateur externe (graphviz ou yEd par exemple).

Graphes bipartis

Une des application du parcours en largeur est de vérifier si un graphe non-orienté est biparti ou non. Pour faire ceci, on effectue un parcours en largeur en coloriant les sommets au fur et à mesure : le premier sommet est colorié en ROUGE, et ces voisins en VERT, et leurs voisins en ROUGE, etc.

Si un sommet reçoit deux couleurs, alors c'est qu'il n'est pas biparti ; et si le parcours termine normalement, alors c'est que le graphe est biparti : un ensemble de sommets ROUGEs et un ensemble de sommets VERTs.

Décrivez votre algorithme avant de l'implanter et de le tester (fonction biparti).

Cette fonction prend en argument un graphe sous forme de liste d'adjacence, et renvoie un tableau de couleur qui donne la couleur de chaque sommet dans le graphe biparti, ou bien le pointeur NULL si le graphe n'est pas biparti.

Diamètre d'un graphe

Une autre application du parcours en largeur est le calcul de la distance entre deux points d'un graphe. Décrivez comment vous vous y prenez, puis programmez une fonction diametre qui devra calculer le diamètre d'un graphe, c'est a dire la plus grande distance entre deux sommets du graphe.

Votre algorithme devra être économe et faire aussi peu de parcours que possible...

Estimez la complexité de votre programme.