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

Question

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

cptpingu · Answer

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é.

Iziwschi · Answer

bonsoir,
merci pour ta réponse. ben au faite   j'ai bien utilisé une matrice d'adjacence qui est générée aléatoirement . en suite selon la les valeur de la matrice j'ai créé une liste chainée. par contre j'ai juste un petit souci de dédoublement dans la matrice. je me rend compte que les arrêtes créées sont en double càd, j'ai  1--5 et 5--1 vu que la graphe n'est pas orienté ca ne le fait pas. 

dans ton message j'ai pas bien compris quand tu dis, " ...remplir aléatoirement la moitié et de l'appliquer par symétrie si celui n'est pas orienté..."  ben au faite tu me donne la solution mais je ne comprend pas trop. 
merci en tout cas d 'avoir pris le temps de me répondre.

cptpingu · Answer

En fait j'ai besoin de plus d'indication pour pouvoir t'aider:
- Est-ce un graphe dynamique ou statique ?
- Tu dois le représenter en matrice d'adjacence, en liste chaînée, ou tu as le choix ? (Je suppose que c'est en liste chaînée).
- Orienté ou non ? (Je suppose que non).

> dans ton message j'ai pas bien compris quand tu dis, " ...remplir 
> aléatoirement la moitié et de l'appliquer par symétrie si celui n'est pas 
> orienté..."  ben au faite tu me donne la solution mais je ne comprend pas trop. 

En fait ce que je voulais te dire, c'est que dans le cas d'un graphe statique et non orienté, il suffit de générer aléatoirement une partie des points de la matrice d'adjacence puis de l'appliquer par symétrie. Un petit dessin pour l'expliquer:

  1 2 3 4 5
1 01 1 0 1
2 110 1 0
3 1 001 1
4 0 1 101
5 1 0 1 11

Ici il suffit de générer aléatoirement la partie rouge et bleu et il est alors facile de deviner la partie verte, par symétrie.

Iziwschi · Answer

bonsoir, plus exactement ce que je cherche a implémenter c'est l 'algorithme de Erdös et rényi.on se fixe un nbr n= |V| de sommet et il existe une arête entre deux sommet u,et v avec une probabilité p . cette proba est la même pour toutes les arêtes. le graphe est apparemment non orieneté. j'ai utilisé donc une matrice d'adjacence . mais pour les arrete j'utilise une liste chainée . je me suis basé sur cette structure, typedef struct arete { int sommet; struct arete * next; }ARETE; ARETE *adjacence; voici ce que j'ai codé jusqu'a maintenant. ce code n'est pas encore compilé. j'éspere que c 'esr pas trop long et surtout je prend pas trop de ton temps. merci ********************************************************************************* ********************************************************************************* #include #include #include #include "graph.h" N=rand_entier (n) //revoie entier entre 0 et n arrete *genere_G_Erdos_renyi() { int tabGraphe [N][N]; arrete * adjacente; matrice_adj=inti_graphe(tabGraphe);// matrice d'adjacence adjacente = transphormMatrice (matrice_adj);// ici on recuppere nos arrtes créées selon matrice adjacence return adjacente; } // fin de la fonction genere G Erdos renyi int inti_graphe(tab_graphe[N][N]) // on creer notre matrice d'adjacence aléatoirement { int i, j , v_matrice; for (i = 0 ; i<=N ; i++) { for (j = i ; j <= N ; j ++) { v_matrice = rand01 (); // on suppose que ici la proba p que sommet i et j forme arete i--j if (v_matrice>0) tab_graphe [i][j] = 1; else{ tab_graphe [i][j] = 0; } } } return tab_graph[i][j]; } arrete *transphormMartrice (int tab_graphe[N][N]) // ici on passera le tableau(matrice ) renvoyé par la fonction init_graphe { int i, j,countr=0; arrete *arrete_debut, *temp *arrete_nouvelle; arrete_debut=creeUneArrete(1,rand_entier(n));// on effecte 1 la valeur du premier sommet avec son poinds, ici rand_entier() // ici on suppose qu'il existe une arrete de depart for (i = 0 ; i<=N ; i++) { for (j = i ; j <= N ; j ++) { if (tab_graphe [j][i] > 0) // ££ { //if (countr == 0) { temp = creeUneArrete (j, rand_entier()); // quand ££ vaut 1 on cree une nouvelle arete on assigne son // au point temp arrete_debut->suiv = temp; } temp->suvi=arrete_nouvelle; } else { temp = creeUneArrete (j, rand_entier); arrete_nouvelle->suiv = temp; } } }// fin de l boucle for de j }// fin de l boucle for de i return arrete_debut; }// fin de la fonction transphorm matrice ***************************************************************** *****************************************************************

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

4 réponses

Votre réponse

Discussions similaires