Algorithme de Tarjan en theorie des graphes Fermé

Question

BonsoirQui saurait m'expliquer même sommairement ou bien encore où puis-je trouver une descrition pas-à-pas de l'algorithme de Tarjanpour déterminer les composantes fortement connexes d'un graphe orienté ?Cet algorithme utilise un "parcours en profondeur d'abord" (DFS, depth first search) puis numérote d'une certaine façon les sommets, je n'en sais guère plus. Le mieux serait un applet Java.Merci.Calaz

calaceite · Answer

Oulala, ça m'étonne pas qu'il y ait pas trop de doc, c'est vraiment non trivial comme algorithme, ça date d'ailleurs de 1972 alors que le thème est rebattu. Pour ceux que ça pourrait intéresser, voici un lien où les explications sont complètes et claires : le Cours "Algorithmes et programmation" de l'Ecole polytechnique, c'est bien dans les vieux pots qu'on fait les meilleures soupes..., bon, le lien :http://www.enseignement.polytechnique.fr/profs/informatique/Jean-Jacques.Levy/poly/main5/node1.html#SECTION00100000000000000000Calaz

Algorithme de Tarjan en theorie des graphes

1 réponse

Discussions similaires