[C]Initialiser un graphe Fermé

Question

Bonjour,je voudrais savoir si quelqu'un pouvait m'indiquer le code C qu'il faut que j'écrive pour avoir la figure si dessus en utilisant les structures suivantesMercitypedef struct noeud {  int n;  struct noeud **tab; /*Tableau de pointeurs sur d'autres noeuds 			transitions sortantes du noeud)*/}Noeud;typedef struct {  Noeud *racine;//Designe un noeud du graphe}Graphe;On supposera que tous les noeuds du graphe sont accessibles à partir de celui désigné par par le pointeur racine de la structure Graphe.Sur la figure, le noeud racine contient 1 (montré par la flèche entrante). Même si ce n'est pas le cas sur la figure, deux noeuds différents peuvent contenir le me entier.   --------|  |        |  |  5---->4  | ^ \   ^^  v/   \ / |->1     /  |   \   / \ |    v /   vv     3---->2

mamiemando · Answer

Le plus simple c'est que tu crées des fonctions qui vont te permettre d'écrire de manière très intuitive la construction de ce graphe particulier. Pour rester le plus général possible il faut associer a chaque sommet un identifiant unique (retourné par add_vertex). unsigned int add_vertex(struct graph g,struct noeud v);void add_edge(struct graph g,int id_src,int id_dst,struct arc e);Le contenu d'un sommet (que ce soit une chaine de caractère, ou un entier dans ton cas, intervient dans la construction du sommet). struct noeud new_vertex(int name);Tu remarqueras que je rajoute une structure "arc" qui encapsule les données relatives à un arc (par exemple un poids), mais tu peux la laisser vide si tu le souhaites.struct arc{  unsigned int weight;};La structure "graph" dont je parle est la structure qui va encapsuler l'ensemble des sommets et des arcs et donc te permettre de les retrouver lors de la construction du graphe. Je pense que ta structure n'est pas très pratique à utiliser et sera peu efficace pour de grands graphes. Je te propose d'utiliser plutôt :struct graph{  unsigned int num_vertices; // le nombre de sommet  struct noeud ** vertices; //tableau de pointeurs sur chaque sommet du graphe}En toute rigueur la notion d'adjacence devrait figurer dans la structure graph et nonn dans la structure sommet mais tu peux t'en sortir comme ça. Si tu es curieux et que tu à l'intention de travailler sur de très gros graphes, tu peux regarder la lib boost (c++) qui est ultra performante pour tout ce qui est graphe.Bonne chance

Paul · Answer

En faite, ce que je voudrais savoir, c'est comment construire ce cas particulier de graphe.Par exemple pour les sommets 1 et 5, est-ce que c'est comme ça, qu'il faut que je fasse pour construire le graphe de la figureint main(void){  Graphe g1,g2,g3,g4,g5;  g1->racine->n = 1;  g->racine->tab[0] = g5->racine;  g->racine->tab[1] = g3->racine;    g5->racine->n = 5;  g->racine->tab[0] = g2->racine;  g->racine->tab[1] = g4->racine;   /* etc..*/  return 0;}Si ce n'est pas comme cela, pourriez-vous m'indiquer comment cela s'écrit ?

mamiemando · Answer

Le problème c'est que ca ne s'écrit pas aussi simplement car les tableaux d'arcs sortants stockés dans tes sommetsne sont pas alloués, donc ce genre d'écriture conduira inévitablement à une erreur de segmentation. C'est pour celà que je t'ai proposé d'écrire des fonctions pour bien découper ton programme et le rendre lisible et facile à manipuler. En particulier, la fonction ajoutant un arc devra allouer tout ce qu'il faut dans tes structures de sommet pour que l'arc soit créé correctement.Je te conseille très fortement de repartir sur les structures et prototypes de fonction que je t'ai proposé sinon tu risques d'avoir rapidement des problèmes... Maintenant tu es libre de faire ce que tu veux ^^Bonne chance

[C]Initialiser un graphe

3 réponses

Discussions similaires