Discussion :

[Nil_ct]

Bonjour,

J'ai un graphe connexe sur lequel j'aimerai enlever des sommets (et donc les arêtes qui y mènent) seulement si cela n'enlève pas la connexité de mon graphe.
Je connais les sommets que je veux tenter d'enlever et je teste si je peux les enlever un par un.

J'ai pensé à un flood-fill mais j'espère que le fait de savoir quel sommet j'enlève me permettra de faire quelque chose de plus efficace. Des suggestions ?

Je n'ai pas de contraintes en mémoire, par contre j'aimerai que ce soit rapide.

Merci d'avance,

Nil

[Jean-Marc.Bourguet]

Je ne vois rien du mieux qu'un parcours commencant a un des sommets joints au sommet enleve et s'arretant des qu'il a atteint tous les autres sommets joints. Il reste a trouver le parcours le plus adequat. Intuitivement et sans info, un BFS me semble le meilleur, mais si tu connais des proprietes du graphe, tu peux peut-etre te batir un calcul de priorite tel qu'un PFS soi mieux.