Graphes connexes
Pour la suite, nous allons modéliser notre labyrinthe sous forme d'un graphe qui possède pour nœuds les cases du labyrinthe. Deux nœuds sont reliés dans le graphe si on peut transiter d'une case à l'autre sans passer par une case intermédiaire.
Implémentation avec une matrice
Avec cette représentation, chaque lignes et chaque colonnes correpondent à un noeud du graphe.
int ** creerMatrice ();
Permet de générer aléatoirement une matrice correspondant à un graphe. Une case d'indice i et j a pour valeur 1 s'il y a une arrete entre les 2 noeuds, 0 sinon.
Compléxité : Θ(N²)
partition_t graphesConnexesMat (int ** M);
Permet de créer la partition associée à la matrice. S'il existe une arrete entre i et j et qu'ils ne sont pas deja dans la meme classe, on fusionne les classes.
Compléxité : Θ(N²)
Implémentation avec un couple (nombre de noeuds, liste des arretes)
Pour la suite du projet, on va laisser de coté la représentation avec une matrice. Pour cette nouvelle représentation, on considère que pour une case de coordonnées (i; j) dans un labyrinthe de taille N, le noeud correspondant a pour valeur i*N+j. Les arêtes sont des couples d'entiers, avec la première composante de ce couple inférieure à la seconde.
typedef struct graphe {
int nbNoeuds;
int i[TAILLE*TAILLE];
int j[TAILLE*TAILLE];
int nbArretes;
} graphe_t;
graphe_t * creerGraphe ();
Permet de générer la liste des arretes.
Compléxité : Θ(N²)
partition_t graphesConnexesGraphe (graphe_t * G);
Permet de créer la partition associée à un graphe en fusionnant les classes s'il existe une arrete.
Compléxité : Θ(N)
Exemples de graphes obtenus
