Question pr graphe non oriente connexe
Ecrire une fct en C,qui prend en entree un graphe non oriente connexe G et un sommet x de G,et qui a pour resultat 1 si x est un point d'articulation de G et 0 sinon.
ici un Point d'articulation de G est un sommet x de G tq la suppression de x dans G rend le graphe induit non connexe(il possede au moins deux composantes connexes)
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
| int est_point_ariculation(graphe_l g, sommet x)
{ int marque[n_max];
sommet y;
int nb_marques;
for(y=0;y<g.n;y++)
marque[y]=0;
marque[x]=1;
if(x==0)
rech_prof(g,1,marque);
else rech_prof(g,0,marque);
nb_marques=0;
for(y=0;y<g.n;y++)
nb_marques=nb_marques+marque[y];
return (nb_marques<g.n);
}
void rech_prof(graphe_l g ,sommet x, int marque[] )
{ liste p;
marque[x]=1;
p=g.a[x];
while(p!=NULL)
{ if(!marque[p->st])
rech_prof(g,p->st,marque);
p=p->suivant;
}
} |
je sais la fct rech_prof va marquer x et marquer tous les sommets y figurant dans la descendance de x..
mais je n`ai pas compris pourquoi ecrire comme ca...
Merci~~
