chemin, arc dans un graphe
Bonjour,
Je dois determiner s'il existe un chemin entre un etat initial et un etat final tel qu'un de ses arcs appartient à un circuit.
existe il un algorithme pour faire çà ? quel est son nom ?
sinon est ce une bonne idée de calculer d'abord la fermeture reflexo-transitive du graphe ( G=(S,A), la fermeture reflexo transitive de G est notée Gt=(S,At) et elle verifie: { (x,y) appartient At <=> il existe un chemin [x,y] dans G})
et de chercher ensuite un circuit dans ce graphe ?
l'algorithme doit avoir la meilleur complexité possible.
Re: chemin, arc dans un graphe
Salut,
Citation:
Envoyé par semaj_james
Bonjour,
Je dois determiner s'il existe un chemin entre un etat initial et un etat final tel qu'un de ses arcs appartient à un circuit.
Ca manque de precision ton message, on sait meme pas sur quoi tu travailles, quelle structure de donnée, état final et état initial de quoi ?
XXiemeciel
Re: chemin, arc dans un graphe
Citation:
Envoyé par semaj_james
Je dois determiner s'il existe un chemin entre un etat initial et un etat final tel qu'un de ses arcs appartient à un circuit.
A partir de la source, tu peux déterminer facilement les noeuds que tu peux atteindre et qui se trouvent dans un circuit.
Symétriquement, en inversant les arcs, tu peux déterminer les noeuds qui conduisent à l'état final et qui se trouve dans un circuit.
S'il existe un noeud qui est atteint à partir de l'état initial et qui permet d'atteindre l'état final, c'est gagné.
