Sujet Précédent Sujet Suivant

PROGRAMMATION D'UN GRAPH

Utilisateur anonyme - 14 sept. 2004 à 14:03
ami7 Messages postés 99 Date d'inscription dimanche 8 août 2010 Statut Membre Dernière intervention 29 juin 2011 - 8 mars 2011 à 12:54

Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/26145-programmation-d-un-graph

ami7 Messages postés 99 Date d'inscription dimanche 8 août 2010 Statut Membre Dernière intervention 29 juin 2011 1
8 mars 2011 à 12:54

je pense que c'est un travail génial mais j'ai pas compris
les codes source car je ne fait pas de c++
y a t'il des codes source relatifs à ce sujet avec Java

???????
merci de m'aidez

mayak2005 Messages postés 6 Date d'inscription dimanche 27 août 2006 Statut Membre Dernière intervention 5 janvier 2008
18 mai 2009 à 14:45

Bonjour,
je suis très intéressée par votre programme mais j'ai un problème de compilation. Pourriez vous m'aider SVP
1>new.obj : error LNK2019: unresolved external symbol "public: __thiscall matrice::~matrice(void)" (??1matrice@@QAE@XZ) referenced in function _main
1>new.obj : error LNK2019: unresolved external symbol "public: void __thiscall Graph::MenuPartie3(void)" (?MenuPartie3@Graph@@QAEXXZ) referenced in function _main
1>new.obj : error LNK2019: unresolved external symbol "public: void __thiscall Graph::MenuPartie2(class matrice &)" (?MenuPartie2@Graph@@QAEXAAVmatrice@@@Z) referenced in function _main
1>new.obj : error LNK2019: unresolved external symbol "public: void __thiscall Graph::MenuPartie1(class matrice &)" (?MenuPartie1@Graph@@QAEXAAVmatrice@@@Z) referenced in function _main
1>new.obj : error LNK2019: unresolved external symbol "public: void __thiscall Graph::MatVal(class matrice &)" (?MatVal@Graph@@QAEXAAVmatrice@@@Z) referenced in function _main
1>new.obj : error LNK2019: unresolved external symbol "public: void __thiscall matrice::afficher(void)" (?afficher@matrice@@QAEXXZ) referenced in function _main
1>new.obj : error LNK2019: unresolved external symbol "public: void __thiscall Graph::Incidence(class matrice &)" (?Incidence@Graph@@QAEXAAVmatrice@@@Z) referenced in function _main
1>new.obj : error LNK2019: unresolved external symbol "public: void __thiscall Graph::afficherG(void)" (?afficherG@Graph@@QAEXXZ) referenced in function _main
1>new.obj : error LNK2019: unresolved external symbol "public: void __thiscall Graph::RemplireGraph(void)" (?RemplireGraph@Graph@@QAEXXZ) referenced in function _main
1>new.obj : error LNK2019: unresolved external symbol "public: __thiscall matrice::matrice(int,int)" (??0matrice@@QAE@HH@Z) referenced in function _main
1>D:\Documents and Settings\mkrichen\My Documents\Visual Studio 2008\Projects\new\Debug\new.exe : fatal error LNK1120: 10 unresolved externals

Utilisateur anonyme
27 déc. 2006 à 22:04

Mooad --> Il faut, et il suffit de faire un parcours du graphe.

Algo:
0 -> marque;
Tant qu'il existe un sommet s non marqué:
++marque;
marquer(s, marque);
Fin tantQue

avec marquer, l'algorithme qui marque tous les descendants d'un noeud. Cet algo peut être récursif, ou utiliser une FIFO/FILO; ici un exemple récursif:

marque -> marque[s];
Pour tout noeud N, tel qu'il existe un arc (s,N)
marquer(N, marque);
Fin pour

Voilu.

Sinon, à me relire plusieurs années après, je constate que j'ai pas mal évolué depuis le temps :)

Salut à tous.

cs_mooad Messages postés 1 Date d'inscription jeudi 27 avril 2006 Statut Membre Dernière intervention 27 décembre 2006
27 déc. 2006 à 21:33

svp je veux un exemple de programme pour l'algorithme de marquage plus ou moins des sommets des graphes pour determiner les composante fortement connexe

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
21 sept. 2004 à 15:50

c'est étonnant, moi j'aurais plutôt cru que c'était l'inverse, étant donné que s'il y a un vertex x,y pr tt x et tt y, ça fait bcp plus de vertices que ds le cas où il y aurait un chemin.

mais enfin, c'est pas moi qui décide des termes ^^

Utilisateur anonyme
21 sept. 2004 à 11:16

après renseignements:
faiblement connexe: pour tout x,y du graphe G, il existe une chaine (x,y)
fortement connexe: pour tout x,y du graphe G, il existe un chemin (x,y)

dans le cadre non orienté, il n'y a pas différence donc on parle juste de connexe ou non connexe.

cs_mehdibou Messages postés 365 Date d'inscription vendredi 24 mai 2002 Statut Membre Dernière intervention 18 octobre 2004
20 sept. 2004 à 17:55

Un graphe connexe se dit d'un graphe non orienté dont tous les sommets sont accessibles depuis tout autre, il ne possède donc qu'une composante connexe. Pour un graphe orienté, il est connexe si le graphe non-orienté qui lui est associé est connexe.
Fortement connexe ne se dit que pour les graphes orientés, si depuis chaque sommet on peut atteindre tous les autres. Un graphe orienté fortement connexe est donc connexe et possède au moins un cycle.

Par contre je n'ai jamais rencontré "faiblement connexe".

keayoub Messages postés 14 Date d'inscription samedi 11 septembre 2004 Statut Membre Dernière intervention 17 septembre 2004
15 sept. 2004 à 01:28

oui c bien vu pour la remarque avec cout<<endl<<endl

merci d'avoir pensée a ca

et pour le graphe avec un seul noeud c pas vraiment pratique car un graphe c au moin 2 noeud sinon c pas un graph même ds les flots il te faux une entrée et une sortie

et c vrai c pour eviter les problemes de la matrice sinon il faut tt revoir

Utilisateur anonyme
15 sept. 2004 à 00:21

Au fait, petites remarques:
cout << endl << endl, on peux aussi faire cout << '\n' << endl, ou encore cout << "\n\n" ou encore avec <<flush si on veux vider le tampon.

void main, c'est pas standart donc pas portable.

Bref, j'ai pas trop regardé le code, mais par contre je fais une remarque:
je crée un graphe à un noeud, je veux le lier à lui même et là, impossible.
Ca ne fait que les graphes simples ? C'est pour éviter les problemes avec les matrices ?

Utilisateur anonyme
15 sept. 2004 à 00:15

Ah bon ? Je vois bien. Nous appelions cela simplement graphes connexes (cas où qque soit (x,y) il existe un chemin x->y) ou non connexe (cas où le graphe est composé de plusieurs composantes connexes).

keayoub Messages postés 14 Date d'inscription samedi 11 septembre 2004 Statut Membre Dernière intervention 17 septembre 2004
14 sept. 2004 à 21:07

bon pour la question et bien c la reponse qu'a donné kirua c la même chose mais plus claire on dit qu'un chemin est fortement connexes ou bien dense car c la même chose si entre chaque couple (x,y) de noeud avec x#y il existe au moin un chemin entre x et y

sachant que ds un graphe fortement connexe 2 noeud ou sommet sont reliés par au moin 2 chemin

1 de x vers y
2 de y vers x

et il ya pas de connexe tt cours
on dis fortement connexe ou bien faiblement connexe ds le cas contraire

et merci pour votre commentaire et si vs avez plus de questions voici mon compte msn
keayoub@msn.com

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
14 sept. 2004 à 17:44

en fait, on dit qu'il est dense, j'avais jamais vu fortement connexe non plus, mais j'imagine que c'est ça.

c'est pas chiffré, mais pour visualiser la chose, dis toi que qd on graphe est dense, ça commence à être VRMNT utile d'utiliser une matrice d'adjacence plutôt que des listes pour stocker les liaisons, parce que ta matrice prendra jamais plus de n² en place (avec n = nb de sommets), alors que tes listes ça va décoler :/

bon, si tu as un graphe directionnel, une "demi matrice" suffira bien entendu.

Utilisateur anonyme
14 sept. 2004 à 17:33

C'est bizarre, jamais vu cette notion en cours de graphes.
Et à partir de quel moment il est "quasiment" complet ?

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
14 sept. 2004 à 17:19

fortement connexe ça veut dire qu'il est quasiment complet (presque tous les sommets sont reliés à presque tous les autres sommets par des côtés) -- à savoir sommet = vertex et côté = edge, on est qd même tjs plus à l'aise en anglais pr ces sujets ^^

Utilisateur anonyme
14 sept. 2004 à 14:03

Je me suis pas attardé dessus mais je le ferais à l'avenir. Ca doit être assez intéressant de lire le code, surtout qu'il requiert pas mal d'objets mathématiques: les matrices pour les mats d'adajacences, etc...
Puis l'implémentation des algos de recherche de chemin le moins couteux, celui du plus courts etc...

Bref très intéressant surtout la partie analyse.

Euh, juste une question: c'est quoi la diff entre fortement connexe et connexe tout cours ?

Discussions similaires

Bibliothèque Vs Librairie

Programmation d'un dictionnaire bilingue en C

programmation du PIC16F877 LCD en mikro C

Graphique à partir de coordonnées stockées dans une bdd MYSQL

programmation pic16f877a + afficheur LCD

Votre réponse

Discussions similaires