Discussion :

[anthony7788]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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~~

[Jedai]

je sais la fct rech_prof va marquer x et marquer tous les sommets y figurant dans la descendance de x..

Non, x est déjà marqué, rech_prof() est un classique parcours en profondeur du graphe partant d'un sommet qui n'est pas x (1 si x == 0, 0 sinon), comme x est déjà marqué au préalable, ce parcours ne passera pas par x, donc si x est un point d'articulation, ce parcours n'atteindra pas tous les noeuds, ce qui est vérifié par la dernière boucle de est_point_articulation().

--
Jedaï

[anthony7788]

Non, x est déjà marqué, rech_prof() est un classique parcours en profondeur du graphe partant d'un sommet qui n'est pas x (1 si x == 0, 0 sinon), comme x est déjà marqué au préalable, ce parcours ne passera pas par x, donc si x est un point d'articulation, ce parcours n'atteindra pas tous les noeuds, ce qui est vérifié par la dernière boucle de est_point_articulation().

--
Jedaï

merci!

mais

c'est quoi(1 si x == 0, 0 sinon)??
if(x==0) ici x==0 cad?
rech_prof(g,1,marque);
else rech_prof(g,0,marque);


si x est un point d'articulation, ce parcours n'atteindra pas tous les noeuds
cad nb_marques<g.n?
quand nb_marques=g.n c'est pas point d'articulation?