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.
Le Tout est souvent plus grand que la somme de ses parties.
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;
Le Tout est souvent plus grand que la somme de ses parties.
représentation d'un graphe
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.