Générer un graphe aléatoirement en langage C

Iziwschi Messages postés 5 Date d'inscription mardi 14 avril 2009 Statut Membre Dernière intervention 11 mai 2011 - 21 avril 2009 à 18:42
Iziwschi Messages postés 5 Date d'inscription mardi 14 avril 2009 Statut Membre Dernière intervention 11 mai 2011 - 23 avril 2009 à 00:59
Bonjour,
je suis débutant en algorithmique, j'essaye depuis ce matin de comprendre comment je peux générer un graphe aléatoirement en langace C mais je ne arrive vraiment pas à comprendre la procédure. je sais qu'on peut utilisé matrice adjacent sommets-arc, mais je ne sais pas comment l'implémenter.
au faite je n'arrive pas a comprendre comment representer les arcs et les sommets, doit je utiliser un tableau, une structure ...

mon bute est de générer un graphe aléatoirement et  afficher ce graphe :
exemple :
soit G(E,V), E = arcs(ou arêtes), et V sommets:
V={1,2,3,4,5,6}ensemble des sommets
E={(1--2)( 2---3)(3--4)(4--5)(5--2)(6--1)} les arcs existant.

Exemple graphe:
1--2       
2---3
3--4
4--5
5--2
6--1

merci de me donner une petite astuce ou de m'éclaircir un peu plus sur la procédure
 à suivre.
-----------
julien

4 réponses

cptpingu Messages postés 3839 Date d'inscription dimanche 12 décembre 2004 Statut Modérateur Dernière intervention 29 juin 2024 124
22 avril 2009 à 16:58
Si tu as une matrice d'adjacence (donc graphe statique), alors c'est extrêmement simple. Il suffit de remplir un tableau a double dimension aléatoirement de 0 ou de 1, si le graphe est orienté, et de remplir aléatoirement la moitié et de l'appliquer par symétrie si celui n'est pas orienté.
Si le graphe est dynamique, alors c'est plus compliqué au niveau de l'implémentation, surtout si celui-ci est non-orienté.
Rejoignez-nous