gilou Modérateur Modzilla | Je ne sais pas, puisque tu ne montre pas comment tu veux calculer le BFS.
En tout cas, je te souhaite du plaisir a gérer les allocations.
J'ai pondu vite fait une soluce à ton exercice:
Code :
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- // On représente le graphe par sa structure en liste d'adjacence
- // Comme donné dans le fichier, on n'a pas besoin de plus
- #define MAXNODES 26
- char Graphe[MAXNODES][MAXNODES+2] = {0};
- // Associe a chaque lettre le sommet correspondant dans Graphe, s'il existe
- char Index[MAXNODES];
- // Lecture et remplissage des structures
- int read_graph(const char *path) {
- FILE *fp;
- if ((fp = fopen(path, "r" )) == NULL) {
- fprintf(stderr, "Error: Cannot open file %s\n", path);
- return EXIT_FAILURE;
- }
- int i;
- for (i = 0; i < MAXNODES; ++i) {
- Index[i] = -1;
- }
- i = 0;
- char line[MAXNODES+3];
- while((fgets(line, MAXNODES+3, fp)) != NULL) {
- char buffer[MAXNODES + 2] = {0};
- if (sscanf(line, "%1[A-Z]-%[A-Z]\n", buffer, buffer+2)) {
- buffer[1] = '-';
- strncpy(Graphe[i], buffer, MAXNODES+2);
- Index[*Graphe[i] - 'A'] = i;
- i++;
- }
- else if (sscanf(line, "%1[A-Z]\n", buffer)) {
- buffer[1] = '-';
- buffer[2] = 0;
- strncpy(Graphe[i], buffer, MAXNODES+2);
- Index[*Graphe[i] - 'A'] = i;
- i++;
- }
- }
- fclose(fp);
- return EXIT_SUCCESS;
- }
- // calcul du BFS
- void BFS() {
- char bfs[MAXNODES*2] = {0};
- int i = 0;
- int current = 0;
- int last = 0;
- // On cherche des noeuds du graphe pas traités
- while (*Graphe[i]) {
- // un nouveau sommet début de graphe
- // pour une composante connexe
- if (Graphe[i][1] == '-') {
- Graphe[i][1] = '+';
- if (last != 0) {
- bfs[last++] = ' ';
- }
- current = last;
- bfs[last++] = *Graphe[i];
- do {
- int j = 2;
- char c;
- // On traite les noeuds adjacent au noeud courant
- // en les ajoutant à bfs s'ils n'y sont pas déjà
- while ((c = Graphe[Index[bfs[current] - 'A']][j])) {
- if (Graphe[Index[c - 'A']][1] == '-') {
- Graphe[Index[c - 'A']][1] = '+';
- bfs[last++] = c;
- }
- ++j;
- }
- } while(bfs[current++]); // et on avance d'un cran dans bfs
- }
- ++i;
- }
- printf("%s\n", bfs);
- }
- int main() {
- if (read_graph("bfs.txt" ) == EXIT_SUCCESS) {
- BFS();
- }
- return 0;
- }
|
A+, ---------------
There's more than what can be linked! -- Iyashikei Anime Forever! -- AngularJS c'est un framework d'engulé! --
|