[C/C++]definition de graphe Fermé

Question

bonjours,

j'aimerais si quelqu'un serait suceptible de m'expliquer ce qu'est un graphe en C svp

mamiemando · Accepted Answer

A ben si tu veux faire du C++ c'est beaucoup plus simple, tu utilises directement la lib boost. Sinon une matrice d'adjacence c'est juste une structure qui à la case (i,j) pointe vers la structure associé à l'arc (i,j). Ca décrit la moitié de ton graphe (les arcs). Il faut en plus stocker le contenu des sommets. Si tu es prêt à passer à boost (librairie gratuite) voici les concepts importants pour débuter. Enjeux Boost c'est vraiment LA librairie à utiliser si tu veux manipuler des gros graphes génériques. Tu manipules les doigts dans le nez des graphes avec des milliers de sommets et de noeuds, avec des structures très propres et plein d'outils super pratiques - la plupart des algorithmes de la théorie des graphes sont déjà implémentés (dijkstra, flot max, composantes fortement connexes...) - il n'y a pas plus rapide - un graphe se définit en quelques lignes de code - c'est un peu déroutant au début mais à l'usage facile à manipuler une fois qu'on a compris les concepts. Afin de ne pas te noyer (et comme je ne sais pas si c'est ce que tu vas utiliser au final), je vais te faire à présent une petite introduction à boost pour que tu vois les concepts, quitte à les réutiliser si tu dois/veux réimplémenter ta propre structure de graphe. Installation Sous linux (sachant que c'est disponible sous windows aussi, cf site de boost) il suffit d'installer le paquet de développement boost. Sous debian il suffit de taper en root : aptitude install libboost-graph-dev Prérequis Il est important que tu saches manipuler une structure template et que tu saches à quoi correspond l'opérateur :: en C++ sinon tu vas rien capter. Il faut aussi que tu saches utiliser ton compilateur de manière un peu plus évoluée car pour compiler un programme avec boost il faut lui spécifier ou se trouvent les headers dans la librairies. Sous linux c'est en général dans /usr/include/boost, donc pour compiler plop.cpp il faut taper : g++ -W -Wall -I/usr/include/boost plop.cpp Terminologie Pour simplifier et que tu perçoives les notations boost, je vais supposer que ta matrice d'adjacence est une matrice, donc que l'on peut décrire un sommet par un entier et un arc par une paire d'entier - l'entier qui identifie un sommet est appelé vertex descriptor - la paire d'entier formée d'un vertex descriptor source et d'un vertex descriptor destination est appelé edge_descriptor - la structure associée au contenu d'un sommet est appelé vertex bundled - la structure asoocié au contenu d'un arc est appelé edge bundled A l'instar de la STL, boost propose d'itérer sur différents ensembles particuliers du graphe - les sommets du graphe (vertex_iterator) - les arcs du graphe (edge_iterator) - les arcs sortants d'un sommet du graphe (out_edge_iterator) - selon la manière dont ta matrice d'adjacence a été choisie tu peux éventuellement avoir aussi un in_edge_iterator (mais c'est 2 fois plus couteux en mémoire). Parfois tu verras dans boost des histoires de traits. Ce sont simplement des structures template qui ne contiennent que des typedef. Utilisation La première étape c'est de définir les structures associées au vertex_bundled et edge_bundled de ton graphe. En effet les graphes boost sont en fait des structures templates (génériques) permettant d'encapsuler n'importe quelle structure de sommet ou d'arc, boost s'occupe juste de stocker intelligemment les données et de te permettre d'y accéder facilement et rapidement. Je vais noter : - g le graphe - v le vertex descriptor d'un sommet - vit le vertex_iterator de ce sommet - node le vertex bundled de ce sommet. - e le edge descriptor d'un arc - eit le edge iterator de ce sommet - link le edge bundled de ce sommet Avec ces notations tu as les équivalences : v <=> *vit node <=> g[v] <=> g[*vit] e <=> *eit link <=> g[e] <=> g[*eit] Les ensembles que je t'ai décris précédemment sont caractérisés par un iterator de début et un iterator de fin. Je vais noter graph_t le type du graphe boost, qu'il faut avoir défini auparavant. Exemples graph_t::vertex_iterator vit,vend; for(boost::tie(vit,vend)=boost::vertices(g);vit!=vend;++vit){ // le sommet courant est associé au vertex iterator vit, je parcours ici les sommets du graphe } graph_t::edge_iterator eit,eend; for(boost::tie(eit,eend)=boost::edges(g);eit!=eend;++eit){ // l'arc courant est associé au edge iterator eit, je parcours ici les arcs du graphe } Si jusque là tu as tout compris et que tu es intéressé par boost, tu peux commencer à regarder un premier exemple ici car je n'ai pas le temps de faire tout le tutoriel en une matinée : https://www.boost.org/doc/libs/1_72_0/libs/graph/example/dijkstra-example.cpp Bonne chance

mamiemando · Answer

Sans plus de précision, j'imagine que tu fais simplement allusion à une structure de donnée qui encapsule un graphe G(V,E) (de la théorie des graphes), c'est à dire
- un ensemble de sommets V
- un ensemble d'arc E qui connecte deux noeuds appartenant à V, éventuellement orienté du sommet source au sommet destination.
https://fr.wikipedia.org/wiki/Th%C3%A9orie_des_graphes

Chaque noeud et chaque arc peut encapsuler un certains nombre d'informations :
Exemple : pour le problème de plus court chemin, les arcs stockent les métriques associées à chaque arc, et les noeuds le nom des sommets.
https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

A noter que la librairie boost permet de manipuler des graphes génériques en C++.
https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/dijkstra_shortest_paths.html

Bonne chance

Tartouffe · Answer

merci pour cet explication est-ce que ceci est juste:
struct noeud{
                       int val;
                       struct noeud t[2];
};
struct graphe{
                        struct noeud *racine;
};

mamiemando · Answer

Ca n'a aucune chance de compiler car tu définis ta structure noeud à partir d'un tableau de struct noeud. Or à ce stade le compilateur ne sais pas quelle taille en mémoire allouer donc ca va planter. La seule façon de faire en C, c'est d'utiliser des pointeurs. En effet un pointeur (une adresse) fait toujours la même taille et peut donc être utilisé.

A priori un graphe n'est pas caractérisé par un noeud racine, c'est juste une sous classe de graphe qui est concerné (les arbres). Dans ton cas je partirais plus sur un truc du genre.

Le plus simple c'est de représenter le graphe par une matrice d'adjacence. Ceci caractérise la représentation d'un graphe. Cette matrice d'adjacence peut être représentée par des listes chaînées croisées, ou directement une matrice. Tu dois programmer impérativement en C ou tu peux faire du C++ ?

Tartouffe · Answer

non non je peut faire du C++
tu pourais me donner la structure d'une matrice d'adjacence stp

[C/C++]definition de graphe

5 réponses

Discussions similaires