00001 /********************************************************************** 00002 ***** Pierre Hyvernat, cours info505 "Algorithmes de graphes" ***** 00003 ***** ***** 00004 ***** Il s'agit des définitions de quelques fonctions pour le TP ***** 00005 ***** en salles machines... ***** 00006 *********************************************************************/ 00007 00008 #include <stdio.h> 00009 #include "graphes.h" 00010 00011 #define HAUTEUR 15 00012 #define LARGEUR 33 00013 00014 00015 /* une structure de données pour les piles et les files */ 00016 struct __case { 00017 int origine ; 00018 int poids ; 00019 int but ; 00020 struct __case *suivant ; 00021 struct __case *precedent ; 00022 } ; 00023 00024 typedef struct __Tile { 00025 struct __case *premier ; 00026 struct __case *dernier ; 00027 } *Tile ; 00028 00029 00030 /* prototype de la fonction qui initialise une tile vide */ 00031 Tile tileVide() ; 00032 00033 /* prototype de la fonction qui insere un arc dans une tile */ 00034 void entile(int, int, int, Tile) ; 00035 00036 /* prototype de la fonction qui enlève le premier élément dans une tile. */ 00037 void detilePremier(Tile, int*, int*, int*) ; 00038 00039 /* prototype de la fonction qui enlève le premier élément dans une tile. */ 00040 void detileDernier(Tile, int*, int*, int*) ; 00041 00042 /* prototype de la fonction qui initialise une grille pleine */ 00043 GrapheListe grillePleine(void) ; 00044 00045 00046 00047 /******************************************************************* 00048 * Les prototypes suivants devront etre definis dans votre fichier * 00049 * $(NOM)-labyrinthes.c * 00050 *******************************************************************/ 00051 00052 00053 /*prototype d'affichage d'une grille donnée par un graphe */ 00054 void afficheGrille(GrapheListe) ; 00055 00056 /* prototype de la fonction deparcours 00057 * elle prend en argument le points de départ du parcours et renvoie l'arbre 00058 * du parcours sous forme d'un graphe 00059 */ 00060 GrapheListe parcours_largeur (GrapheListe G,int a,int b) ; 00061 00062 GrapheListe parcours_profondeur (GrapheListe G,int a,int b) ; 00063 00064 00065 /* algorithme de Kruskal */ 00066 GrapheListe kruskal (GrapheListe G) ; 00067 00068 /* facultatif : 00069 GrapheListe prim (GrapheListe G) ; 00070 */ 00071 00072 00073
1.5.5