Meilleure réponse
Un composant fortement connecté (SCC) dans un graphe orienté est soit un cycle ou un sommet individuel.
Nous appliquons DFS sur le graphe et gardons une trace de deux propriétés pour chaque nœud dans larbre DFS produit: 1. Son heure (ou ordre) de sa première découverte dans DFS. ( Disons p1) 2. Lordre de lancêtre le plus ancien quil peut atteindre (disons p2) Au départ, les deux sont identiques pour chaque nœud. Alors que la première propriété reste constante, la deuxième peut être mise à jour pendant les appels DFS récursifs et utilisée pour rechercher les arêtes arrière vers les ancêtres. Pour tout sommet, si les deux sont identiques après des appels DFS récursifs à tous ses sommets adjacents, il sagit soit de 1. Un sommet individuel qui ne fait partie daucun cycle. OU 2. Une partie dun cycle et donc tout son descendant (dans larbre DFS produit) peut latteindre (ne peut pas atteindre ses ancêtres). En dautres termes, nous pouvons commencer et terminer à ce nœud. Dans le 2ème cas, nous pouvons garder une trace de tous les descendants à imprimer.
cette animation aide à comprendre lexplication (le premier entier est p1, le second est p2):
@ Fichier: Algorithme de Tarjan « Animation.gif
Explication détaillée et implémentation c ++: Tarjan » s Algorithme pour trouver des composants fortement connectés – GeeksforGeeks
PS: Cet algorithme est très similaire à la recherche de points darticulation, de ponts et de graphiques biconnectés. Donc, les apprendre en premier peut vous aider à avoir une meilleure intuition pour lalgorithme. http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/ http://www.geeksforgeeks.org/bridge-in-a-graph/
Réponse
Lalgorithme prend un graphe orienté comme entrée, et produit une partition des sommets du graphe dans les composants fortement connectés du graphe. Chaque sommet du graphe apparaît dans exactement lun des composants fortement connectés. Tout sommet qui nest pas sur un cycle dirigé forme un composant fortement connecté à lui tout seul: par exemple, un sommet dont le degré dentrée ou de sortie est égal à 0, ou tout sommet dun graphe acyclique.
Le Lidée de base de lalgorithme est la suivante: une recherche en profondeur commence à partir dun nœud de départ arbitraire (et les recherches en profondeur suivantes sont effectuées sur tous les nœuds qui nont pas encore été trouvés). Comme dhabitude avec la recherche en profondeur dabord, la recherche visite chaque nœud du graphique une seule fois, refusant de revoir tout nœud déjà exploré. Ainsi, la collection darbres de recherche est une forêt étendue du graphe. Les composants fortement connectés seront récupérés comme certains sous-arbres de cette forêt. Les racines de ces sous-arbres sont appelées les «racines» des composants fortement connectés. Tout nœud dun composant fortement connecté peut servir de racine, sil se trouve quil sagit du premier nœud du composant découvert par la recherche.