Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
2312 connectés 

  FORUM HardWare.fr
  Programmation
  C

  [C] parcours en largeur \ profondeur

 
 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

[C] parcours en largeur \ profondeur

n°2269397
alakaab
Posté le 09-11-2015 à 18:48:06  profilanswer
 

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
mood
Publicité
Posté le 09-11-2015 à 18:48:06  profilanswer
 

n°2269399
gilou
Modérateur
Modosaurus Rex
Posté le 09-11-2015 à 22:09:37  profilanswer
 

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! --  Le capitaine qui ne veut pas obéir à la carte finira par obéir aux récifs. -- Il ne faut plus dire Sarkozy, mais Sarkozon -- (╯°□°)╯︵ ┻━┻
n°2269437
alakaab
Posté le 10-11-2015 à 16:26:37  profilanswer
 

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

n°2269507
gilou
Modérateur
Modosaurus Rex
Posté le 11-11-2015 à 19:56:42  profilanswer
 

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! --  Le capitaine qui ne veut pas obéir à la carte finira par obéir aux récifs. -- Il ne faut plus dire Sarkozy, mais Sarkozon -- (╯°□°)╯︵ ┻━┻
n°2269508
gilou
Modérateur
Modosaurus Rex
Posté le 11-11-2015 à 19:59:25  profilanswer
 

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! --  Le capitaine qui ne veut pas obéir à la carte finira par obéir aux récifs. -- Il ne faut plus dire Sarkozy, mais Sarkozon -- (╯°□°)╯︵ ┻━┻

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  C

  [C] parcours en largeur \ profondeur

 

Sujets relatifs
Decryptage C++[C++11] fonction renvoyant une reference sur un tableau de 10 string
Programmation C - conditionnelle[HTML5/CSS] Menu sur toute la largeur du site
C tri par fusion[C#] Découpage de chaine
aligner verticalement colonne en CBesoin d'aide en C
[C#] Problème récup fabrique de la classe COM 
Plus de sujets relatifs à : [C] parcours en largeur \ profondeur

Forum MesDiscussions.Net, Version 2010.2
(c) 2000-2011 Doctissimo
Page générée en 0.095 secondes

Copyright © 1997-2025 Groupe LDLC (Signaler un contenu illicite / Données personnelles)