[C] parcours en largeur \ profondeur

parcours en largeur \ profondeur [C] - C - Programmation

Marsh Posté le 09-11-2015 à 18:48:06    

Bonjour ,  
 
je suis un debutant en C et je suis entrain de faire un exercice sur les BFS et DFS mais j´ai quelque soucis avec .. bon voila l´exercice en question :  
 
 
Your program shall read in a graph in adjacency list format and perform a breadth first search (BFS) on the graph, starting at the node first read. Each node's name is a single letter 'A'-'Z', so you can safely assume less than 27 nodes for your graph. The format of each line to be read in is specified as
  <
nodeName>-<string of neighboring node names>\n   (see example below).
 
The requested output  of your program is one line of node names followed by '\n', in which the order of names represents one possible exploration following breadth first search.
 
Note (1): for most inputs several different outputs are possible. Here we only ask you to find one of them!
Note (2): all graphs here are undirected, i.e. if a connection A-...B... exists you will also find a connection B-...A....
 
 inputs et output doivent etre comme ca : http://hpics.li/94c1e3a  
 
 
 
 
y´a un truc que je comprend pas  .... vu qu´on me donne pas le nombre des chaines de caractere comment suis je censé faire une liste d´adjacence ?  
 
 
 
 
sinon voila le code que j´ai fait pour la creer la liste d´adjacence en me basant sur un exple  ;  
 

Code :
  1. #include<stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  5. typedef struct node
  6. {
  7.     struct node *next;
  8.     char vertex;
  9.    
  10. }node;
  11. char s[27]; 
  13. //heads of linked list
  14. node *G[20]; 
  16. //insert an edge (vi,vj) in te adjacency list
  18. void insert(int,char[],int);
  20. void BFS(int,int) ;
  23. int main()
  24. {
  25.     int i,n; int v=0;
  26.  
  27.     //initialise G[] with a null
  28.  
  29.     for(i=0;i<=27;i++)
  30.     {
  31.         G[i]=NULL;
  32.     }
  33.    
  34.          scanf("%s",s);
  35.            
  36.              n=strlen(s);
  37.              insert(v,s,n);
  38.              v=v+1;
  39.          
  40.          return 0;
  41. }
  43. void insert(int vi,char s[],int n)
  44. {
  45.     node *p,*q,*d; int i=2 ;
  46.    
  47.     //acquire memory for the new node
  48.     q=(node*)malloc(sizeof(node));
  49.     q->vertex=s[0];
  50.    
  51.     q->next=NULL;
  52.  
  53.     //insert the node in the linked list number vi
  54.     if(G[vi]==NULL)
  55.        {
  56.           G[vi]=q;
  57.        }
  58.    
  59.     while (i<n){
  60.         d=(node*)malloc(sizeof(node));
  61.     d->vertex=s[i];
  62.     d->next=NULL;
  63.    
  64.         p=G[vi];
  65.      
  66.         while(p->next!=NULL)
  67.             p=p->next;
  68.         p->next=d;
  69.         i++;
  70.       }
  71.      
  72.     }


 
 
 
Je sais pas c´est tres claire mais bon je suis un peu confus c´est pour ca  
 
Merci


Message édité par gilou le 09-11-2015 à 21:30:00
Reply

Marsh Posté le 09-11-2015 à 18:48:06   

Reply

Marsh Posté le 09-11-2015 à 22:09:37    

Tu n'as pas besoin de te fatiguer a implémenter le graphe en mémoire de manière complexe juste pour répondre à la question:
En supposant ton graphe connexe (et je suppose que ça suffit pour ton exercice)
Tu as juste besoin de calculer la distance minimale de chaque sommet au sommet de base.
A toi de trouver une manière simple de procéder.
 
A+,
 
 
 


---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 10-11-2015 à 16:26:37    

Merci pour la reponse ! mais est ce que c´est possible de realiser un BFS a partir du code que j´ai fait ?

Reply

Marsh Posté le 11-11-2015 à 19:56:42    

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 :
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  5. // On représente le graphe par sa structure en liste d'adjacence
  6. // Comme donné dans le fichier, on n'a pas besoin de plus
  7. #define MAXNODES 26
  8. char Graphe[MAXNODES][MAXNODES+2] = {0};
  9. // Associe a chaque lettre le sommet correspondant dans Graphe, s'il existe
  10. char Index[MAXNODES];
  12. // Lecture et remplissage des structures
  13. int read_graph(const char *path) {
  14.     FILE *fp;
  16.     if ((fp = fopen(path, "r" )) == NULL) {
  17.         fprintf(stderr, "Error: Cannot open file %s\n", path);
  18.         return EXIT_FAILURE;
  19.     }
  21.     int i;
  22.     for (i = 0; i < MAXNODES; ++i) {
  23.         Index[i] = -1;
  24.     }
  26.     i = 0;
  27.     char line[MAXNODES+3];
  28.     while((fgets(line, MAXNODES+3, fp)) != NULL) {
  29.         char buffer[MAXNODES + 2] = {0};
  30.         if (sscanf(line, "%1[A-Z]-%[A-Z]\n", buffer, buffer+2)) {
  31.             buffer[1] = '-';
  32.             strncpy(Graphe[i], buffer, MAXNODES+2);
  33.             Index[*Graphe[i] - 'A'] = i;
  34.             i++;
  35.         }
  36.         else if (sscanf(line, "%1[A-Z]\n", buffer)) {
  37.             buffer[1] = '-';
  38.             buffer[2] = 0;
  39.             strncpy(Graphe[i], buffer, MAXNODES+2);
  40.             Index[*Graphe[i] - 'A'] = i;
  41.             i++;
  42.         }
  43.     }
  45.     fclose(fp);
  46.     return EXIT_SUCCESS;
  47. }
  49. // calcul du BFS
  50. void BFS() {
  51.     char bfs[MAXNODES*2] = {0};
  53.     int i = 0;
  54.     int current = 0;
  55.     int last = 0;
  56.     // On cherche des noeuds du graphe pas traités
  57.     while (*Graphe[i]) {
  58.         // un nouveau sommet début de graphe
  59.         // pour une composante connexe
  60.         if (Graphe[i][1] == '-') {
  61.             Graphe[i][1] = '+';
  62.             if (last != 0) {
  63.                 bfs[last++] = ' ';
  64.             }
  65.             current = last;
  66.             bfs[last++] = *Graphe[i];
  68.             do {
  69.                 int j = 2;
  70.                 char c;
  71.                 // On traite les noeuds adjacent au noeud courant
  72.                 // en les ajoutant à bfs s'ils n'y sont pas déjà
  73.                 while ((c = Graphe[Index[bfs[current] - 'A']][j])) {
  74.                     if (Graphe[Index[c - 'A']][1] == '-') {
  75.                         Graphe[Index[c - 'A']][1] = '+';
  76.                         bfs[last++] = c;
  77.                     }
  78.                     ++j;
  79.                 }
  80.             } while(bfs[current++]); // et on avance d'un cran dans bfs
  81.         }
  82.         ++i;
  83.     }
  84.     printf("%s\n", bfs);
  85. }
  87. int main() {
  88.     if (read_graph("bfs.txt" ) == EXIT_SUCCESS) {
  89.         BFS();
  90.     }
  91.     return 0;
  92. }


 
A+,


---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 11-11-2015 à 19:59:25    

Note:
J'ai supposé que les données en input seront toujours valide, ce qui hors du contexte d'un exo, et dans la vie réelle, a toute les chances de se révéler faux :D
 
A+,


---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed