Discussion :

[abdelkaderg54]

...tout le monde ..
Comment pourais je faire pour declaré une structure de graph sachant que l'implimantation est dans une liste d'adjaçance
Merci ..

[c-candide]

...tout le monde ..
Comment pourais je faire pour declaré une structure de graph sachant que l'implimantation est dans une liste d'adjaçance
Merci ..

Il existe de nombreuses façon de faire, ça dépend de ce dont tu as besoin.
Un graphe, c'est un ensemble de relation entre des paires (ou des couples si c'est un graphe orienté) d'objets. Déjà la question est de savoir si tu acceptes d'identifier tes objets à des entiers, sinon il te faudra coder une liste d'adjacence générique mais c'est quand même plus compliqué. Ensuite, on dit liste d'adjacence mais cela n'est pas forcément à prendre au sens informatique de "liste chaînée". Beaucoup d'ouvrages font comme cela mais vu les algorithmes qu'ils développent, la liste chaînée est totalement inutile voire inintéressante (lenteur d'accès). Pour décider si tu as besoin d'une liste chainée, demande-toi si les algorithmes que tu veux écrire nécessitent la suppression ou l'ajout de sommets (attention, c'est souvent coûteux et en fait, on peut souvent s'en passer).

Tu peux par exemple déclarer un graphe comme ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
struct graphe
  {
    /*
    Les sommets sont numerotes de 1 a nb_sommets.
    Chaque liste d'adjacence commence par le numero du sommet a
    qui les sommets sont adjacents.
    Donc si d est le degre de v, on a :
    v est un tableau ayant d+1 membres et la liste des sommmets adjacents
   a v va de v[1] a v[d].
    */
    int **listes;
    int *degres;
    int nb_sommets;
  };

listes[k] (avec k>0, convenance personnelle) est le tableau des éléments adjacents au sommet numéroté k.
degrés est le tableau des degrés sortants. Avec nb_sommets, ça permet de parcourir la liste facilement.