Graphes en C

Version imprimable

15/02/2008, 16h54
linda8080

Graphes en C

bonjour,

je cherche un exemple de programme des graphe en c.

merci d'avance
15/02/2008, 17h17
hegros

quoi comme exemple parce que les graphes c'est vaste on les utilise pour un tas de chose
15/02/2008, 17h50
Melem

Tu devrais peut-être commencer par les tutoriaux (que tu pourras trouver sur ce site) avant de faire des programmes. Et puis d'abord tu parles bien des graphes en maths/algos et structures de données ou de bien de graphes en représentation graphique?
15/02/2008, 18h28
linda8080

c'est le cas des graphes avec des structures de données . je vous serais reconnaissante

j'ai toutes les fonction relatives au graphes avec des structures et je veux avoir un programme pricipales qui va les regrouper pour faire un graphe !!! et verifier s'il existe un chemin d'un sommet vers un autre et aussi pour supprimer un ars ou un sommet
15/02/2008, 18h40
hegros

mais si tu as tout c'est parfait c'est comme si tu avais les briques de ta maison et qu'il manquerait à les poser

montre nous les premières que tu as posé

voici le code des differente fonction relatives au graphes : ajouter un sommet , ajouter un arc ................................

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
typedef struct strelem
{
struct strelem *s1;
int v;
struct strelsm *s2;
} Strelem,*Elem, *Graphe;
//---------------------------------------------------------------------------
typedef struct strelsm
{
int v;
struct strelsm *s2;
} Strelsm,*Elem, *Graphe;
//----------------------------------------------------------------------------
typedef struct maillon
{
        int val;
        struct maillon *suiv;
        } Maillon, *Ens;
 
//-----------------------------------------------------------------------------
Ens Ensvide(void)
{
    Ens e=NULL;
    return e;
}
//-----------------------------------------------------------------------------
#define faux 0;
#define vrai 1;
 
typedef int Booleen;
//------------------------------------------------------------------------------
Booleen appartient(int a, Ens e)
{
 
{if (e==NULL) return faux;
if (e->val==a) return vrai;
return apprtient (a,e->suiv);
 
}
//------------------------------------------------------------------------------
Booleen EstVide (Ens e)
{
        if (e==NULL) return vrai;
        return faux;
        }
//-----------------------------------------------------------------------------
int cardianl (Ens e)
{
    int i=0;
    while (e!=NULL)
    { i++;
      e=e->suiv;
    }
return i;
}
//--------------------------------------------------------------------------------
Ens inserer(int a, Ens e)
{
    Ens m;
    if (appartient (a,e)) return e;
    m=(maillon*)malloc (sizeof (Maillon))
    m->val=a;
    m->suiv=e;
    return m;
}
//----------------------------------------------------------------------------------
Ens supprimer (int a , Ens e)
{
    Ens save;
    if (!appartient (a,e)) return e;
    if (e->val==a) {
                   save=e;
                   e=e->suiv;
                   free(save);
                   return (e)
                   }
    e->suiv=supprier(a,e);
    return e;
}
//-------------------------------------------------------------------------------------
typedef struct eltens
{ 
   int n;
   struct eltens *suiv;
}maillonEns, *Ens;
//-----------------------------------------------------------------------------------
typedef struct eltgraphe
{ int v;
struct eltgraphe *S1;
Ens s2;
} maillongraphe, *Graphe;
 
//--------------------------------------------------------------------------------
Graphe graphnouv (void)
{ return (Graphe)NULL;
}
Booleen exs(Graphe g, int x)
{ 
        if vide(g)) return faux;
        if (g->v==x) return vrai;
        return exs(d->S1,x); 
 }
//------------------------------------------------------------------------------------
Booleen exa(Graphe g, int x, int y)
{
        Graphe aux=g;
        if (!exs(g,x)|| !exs(g,y)) return faux;
        while (aux->v !=x)
        aux=aux->Ss;
        return (appartient (aux->S1, y);
        }
 
 //--------------------------------------------------------------------------------------
 int de( Graphe g , int x)
 { Graphe aux =g; 
 if (!exs(g,x)) return 0;
 while (aux->v !=x)
 aux= aux ->S1;
 return cardinal (aux->Ss);
}
 
 //-------------------------------------------------------------------------------------       
      int di (Graphe g, int x)
      {
          Graphe aux=g;
          int cpt=0;
          while (aux ! NULL)  
		  {if apparient(aux->S1,x) cpt++;
		  aux->S1;
		  }
		  return cpt;
	  }
 
//------------------------------------------------------------------------------------------
 
Graphe adjs(Graphe g, int x)
{
	Graphe m;
	if (exs (g,x) return g;
 
	m=(maillongraphe *)malloc(sizeof (maillonGraphe))
		if( m==NULL)
		{
			printf ("plus de place memoie");
	        exit (0);
	   }
 
   m->v=x;
 
if (vide(g))
{
	m->S1=NULL;
	m->S2=ensnouv();
	return m;
 
}
     if //-------
   {
	   m->S1=g;
	   m->S2=ensnouv;
	   return m
   }
g->S1=adjs(g->S1, x);
return g;
}
 
//-------------------------------------------------------------------------------------------------
Graphe adja (Graphe g, int x, int y)
{
	Graphe aux=g;
	if(!exs (g,x) || !exs (g,y)) return g;
	while (aux->v!=x)
		aux=aux->S1;
	aux->S2=inserer(aux->S2,y);
	return g;
}
//-----------------------------------------------------------------------------------------------------
 
Graphe sups(Graphe g , int x)
{
	if (!exs(g,x)) return g;
	if (de(g,x)!=0 || di(g,x)!=0)
	{
		printf ("sommet relie à un arc");
		return g;
	}
 
	if vide (g) return g;
	if (g->v==x) return g->S1;
	g->S1=sups(g->S1,x);
	return g;
}
//-----------------------------------------------------------------------------------------------
 
Graphe supa(graphe g int x, int y)
{
	Graphe aux=g;
	if (!exa(g,x,y) return g;
	while (!vide (aux))
	{
		if (aux->v==x)
		{
			aux->S2=supelement(aux->S2,y);
			break;
			aux=aux->S1;
		}
		return g
	}
}
 
//--------------------------------------------------------------------------------------------------
 
//ensemble des successeur 
 
Ens esuc(Graphe g, int x)
{
	while (g->v!=x)
		g=g->S1;
	return g->S2;
}
//--------------------------------------------------------------------------------------------------------
 
// ensemble des sommets 
Ens  eg(Graphe g)
{
	Ens e=ensnouv();
	while (!vide(g))
	{
		e=inserer (e, g->v);
		g=g->S1
	}
	return e;
}
//----------------------------------------------------------------------------------------------------------
 
 
Ens parcprof(Graphe g, int x)
{
	Ens e,l;
	e=ensnouv();
	l=ensnouv();
	e=inserer(e,x)
		return parcprof(g,e,l);
}
//--------------------------------------------------------------------------------------------------------------
Ens parcfrofe(Graphe g, ens e, Ens l)
{
	int z; Ens l1;
	if (vide(e)) return l;
	z=choix (e);
	if (appartient(z,l))  l1=l;
	else l1=parcprofe(g,esuc(g,z), inserer(z,l));
	return parcprofe(g,supprimer(e,z),l1)
}
 
//------------------------------------------------------------------------------------------------------
boolleen chemin(Graphe g, int x, int y)
{
	Ens e1,e2;
	e1=esuc(g,x)
	e2=parcprofe(g,e1,ensnouv());
	return (appartient (e2,y));
}
 
//----------------------------------------------------------------------------------------------------------

alors que pensez vous de ce code !! est ce qu'il est bien fait !!

d'accord je vais le commenter tout de suite ok

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
 
typedef struct strelem
{
struct strelem *s1;
int v;
struct strelsm *s2;
} Strelem,*Elem, *Graphe;
//---------------------------------------------------------------------------
typedef struct strelsm
{
int v;
struct strelsm *s2;
} Strelsm,*Elem, *Graphe;
//----------------------------------------------------------------------------
typedef struct maillon
{
        int val;
        struct maillon *suiv;
        } Maillon, *Ens;
 
//-----------------------------------------------------------------------------
Ens Ensvide(void)
{
    Ens e=NULL;
    return e;
}
//-----------------------------------------------------------------------------
#define faux 0;
#define vrai 1;
 
typedef int Booleen;
//------------------------------------------------------------------------------
Booleen appartient(int a, Ens e) // si un sommet appartient au graphe
{
 
{if (e==NULL) return faux;
if (e->val==a) return vrai;
return apprtient (a,e->suiv);
 
}
//------------------------------------------------------------------------------
Booleen EstVide (Ens e)
{
        if (e==NULL) return vrai;
        return faux;
        }
//-----------------------------------------------------------------------------
int cardianl (Ens e)
{
    int i=0;
    while (e!=NULL)
    { i++;
      e=e->suiv;
    }
return i;
}
//--------------------------------------------------------------------------------
Ens inserer(int a, Ens e)   //inserer un sommer dans un graphe 
{
    Ens m;
    if (appartient (a,e)) return e;
    m=(maillon*)malloc (sizeof (Maillon))
    m->val=a;
    m->suiv=e;
    return m;
}
//----------------------------------------------------------------------------------
Ens supprimer (int a , Ens e)  //supprimer un sommet dans un graphe 
{
    Ens save;
    if (!appartient (a,e)) return e;
    if (e->val==a) {
                   save=e;
                   e=e->suiv;
                   free(save);
                   return (e)
                   }
    e->suiv=supprier(a,e);
    return e;
}
//-------------------------------------------------------------------------------------
typedef struct eltens
{ 
   int n;
   struct eltens *suiv;
}maillonEns, *Ens;
//-----------------------------------------------------------------------------------
typedef struct eltgraphe  // definir la structure d'un graphe 
{ int v;
struct eltgraphe *S1;
Ens s2;
} maillongraphe, *Graphe;
 
//--------------------------------------------------------------------------------
Graphe graphnouv (void)  // un nouveau graphe
{ return (Graphe)NULL;
}
Booleen exs(Graphe g, int x)
{ 
        if vide(g)) return faux;
        if (g->v==x) return vrai;
        return exs(d->S1,x); 
 }
//------------------------------------------------------------------------------------
Booleen exa(Graphe g, int x, int y)   // si un arc (x,y) existe 
{
        Graphe aux=g;
        if (!exs(g,x)|| !exs(g,y)) return faux;
        while (aux->v !=x)
        aux=aux->Ss;
        return (appartient (aux->S1, y);
        }
 
 //--------------------------------------------------------------------------------------
 int de( Graphe g , int x)    // le degré exterieur  d'un sommet
 { Graphe aux =g; 
 if (!exs(g,x)) return 0;
 while (aux->v !=x)
 aux= aux ->S1;
 return cardinal (aux->Ss);
}
 
 //-------------------------------------------------------------------------------------       
      int di (Graphe g, int x)  //degré interieur 
      {
          Graphe aux=g;
          int cpt=0;
          while (aux ! NULL)  
		  {if apparient(aux->S1,x) cpt++;
		  aux->S1;
		  }
		  return cpt;
	  }
 
//------------------------------------------------------------------------------------------
 
Graphe adjs(Graphe g, int x)  // ajouter un sommet a un graphe 
{
	Graphe m;
	if (exs (g,x) return g;
 
	m=(maillongraphe *)malloc(sizeof (maillonGraphe))
		if( m==NULL)
		{
			printf ("plus de place memeoire");
	        exit (0);
	   }
 
   m->v=x;
 
if (vide(g))
{
	m->S1=NULL;
	m->S2=ensnouv();
	return m;
 
}
     if 
   {
	   m->S1=g;
	   m->S2=ensnouv;
	   return m
   }
g->S1=adjs(g->S1, x);
return g;
}
 
//-------------------------------------------------------------------------------------------------
Graphe adja (Graphe g, int x, int y)  // ajouter un arc a un graphe 
{
	Graphe aux=g;
	if(!exs (g,x) || !exs (g,y)) return g;
	while (aux->v!=x)
		aux=aux->S1;
	aux->S2=inserer(aux->S2,y);
	return g;
}
//-----------------------------------------------------------------------------------------------------
 
Graphe sups(Graphe g , int x)  /: supprimer un sommet d'un graphe 
{
	if (!exs(g,x)) return g;
	if (de(g,x)!=0 || di(g,x)!=0)
	{
		printf ("sommet relie à un arc");
		return g;
	}
 
	if vide (g) return g;
	if (g->v==x) return g->S1;
	g->S1=sups(g->S1,x);
	return g;
}
//-----------------------------------------------------------------------------------------------
 
Graphe supa(graphe g int x, int y)  // supprimer un arc dans un graphe 
{
	Graphe aux=g;
	if (!exa(g,x,y) return g;
	while (!vide (aux))
	{
		if (aux->v==x)
		{
			aux->S2=supelement(aux->S2,y);
			break;
			aux=aux->S1;
		}
		return g
	}
}
 
//--------------------------------------------------------------------------------------------------
 
//ensemble des successeur 
 
Ens esuc(Graphe g, int x)
{
	while (g->v!=x)
		g=g->S1;
	return g->S2;
}
//--------------------------------------------------------------------------------------------------------
 
// ensemble des sommets 
Ens  eg(Graphe g)
{
	Ens e=ensnouv();
	while (!vide(g))
	{
		e=inserer (e, g->v);
		g=g->S1
	}
	return e;
}
//----------------------------------------------------------------------------------------------------------
 
 
Ens parcprof(Graphe g, int x)
{
	Ens e,l;
	e=ensnouv();
	l=ensnouv();
	e=inserer(e,x)
		return parcprof(g,e,l);
}
//--------------------------------------------------------------------------------------------------------------
Ens parcfrofe(Graphe g, ens e, Ens l)
{
	int z; Ens l1;
	if (vide(e)) return l;
	z=choix (e);
	if (appartient(z,l))  l1=l;
	else l1=parcprofe(g,esuc(g,z), inserer(z,l));
	return parcprofe(g,supprimer(e,z),l1)
}
 
//------------------------------------------------------------------------------------------------------
boolleen chemin(Graphe g, int x, int y)
{
	Ens e1,e2;
	e1=esuc(g,x)
	e2=parcprofe(g,e1,ensnouv());
	return (appartient (e2,y));
}
 
//----------------------------------------------------------------------------------------------------------