Bonjour à tous,

Je cherche à savoir comment représenter un graphe pondéré avec une liste chaînées.

Supposons un arc orienté, d'un poids de 23. 

Est ce que cette représentation est elle correct ?

Désolé si la question parait bête mais je vous j'avoue que je n'arrive pas très bien à le concevoir...

oua_lid a écrit:

Bonjour à tous,

Je cherche à savoir comment représenter un graphe pondéré avec une liste chaînées.

Supposons un arc orienté, d'un poids de 23. 

Est ce que cette représentation est elle correct ?

Désolé si la question parait bête mais je vous j'avoue que je n'arrive pas très bien à le concevoir...

Je ne sais pas ce que tu veux faire de ton graphe. Flot maximum? Plus court chemin? Etc.

On ne peut pas chaîner les arcs seuls, il faut ajouter les noeuds.

Je suggère des structures comme:

typedef struct noeud noeud;

typedef struct arc arc;

noeud struct {

   arc *entrant;

   arc *sortant;

   arc *listesortants;

   char *identificateur;

};

arc struct {

   double flot;

   double capacite;

   noeud *origine;

   noeud *destination;

   arc *suivant;

};

Les arcs sortants du noeud sont dans une liste dont le chaînage est fait dans les arcs.

Après la construction, tu mets les arcs sortants à NULL.

Pour faciliter la construction (j'espère), tu peux construire un tableau trié de pointeurs vers les noeuds.

Pour vérifier si tu ne boucle pas dans tes parcours, tu dois avoir arc sortant == NULL quand tu arrives sur le noeud.

Tu auras un chaînage du genre:

noeud > arc > noeud > arc > ... > noeud

J'espère avoir été relativement clair

Je te remercie une nouvelle fois pierre ! :-)

C'est vraiment de la curiosité ... Je cherchais à comprendre comment, d'un point de vu purement informatique, était représenter un graphe mais plus centré sur l'allocution de la mémoire.

Je sais que les listes d'adjacence utilise des tableaux qui pointent vers de liste chaînés. c-a-d chaque case du tableau correspond à un noeud. et pointe vers une liste chaînés qui sont les successeurs. Mais concernant le poids des arcs. comment cela se passe ?

En python je code un dictionnaire de tel manière 

graphe = {1 : {2 : 30}, 2 : {1 : 15}}

le sommet 1 est relié au sommet 2 pour un poids de 30 (et resp (2,1) = 15 )

Je ne connais pas Python, donc je te fais confiance là-dessus.

Ce que tu décris ressemble plus à un arbre qu'à un réseau. Si c'est le cas, tu n'aurais pas besoin d'arcs. Je pense que tu peux mettre le poids dans chacun des fils de chaque noeud.

Le poids de la racine pourrait être 0, par exemple.

Les noeuds fils seraient chaînés comme je l'ai fait pour mes arcs.

On pourrait avoir quelque chose du genre:

noeud struct {

 noeud *monPere;

 noeud filsCourant;

 noeud *listeFils:

 double lePoids;

};

Il reste un petit problème, comment représente-on les feuilles dans ce cas? Je ne me rappelle pas la syntaxe des structures avec des case. Tu peux toujours ajouter un élément du genre:

 feuille *maFeuille;

et mettre le poids négatif pour l'indiquer.

Ouach! Je n'aime pas cela!

Si cela fonctionne, on pourrais penser à ceci:

altNoeud struct {

 case siFeuille: *feuille;

 case siNoeud *noeud;

};

Et tes noeuds auraient l'air de ceci:

noeud struct {

 noeud monPere;

 altNoeud *divers;

  noeud *listeNoeuds;

 double lePoids;

};

Dans le cas des feuilles, listeNoeuds vaut NULL.

Les case dans les struct ça ne marche pas! Voir le lien suivant pour les union:

https://zestedesavoir.com/tutoriels/755/le-langage-c-1/notions-avancees/les-unions/

Le langage C est tout de même plus flexible avec les types de pointeurs.

On pourrais faire:

union {

 noeud *n;

 feuille *f;

} altNoeud;

On pourrait avoir:

leNoeud.altNoeud.n = unNoeud;

leNoeud.altNoeud.f = uneFeuille;