Algorithme de Tarjan

Graphe original
Questions
  1. Appliquer l'algorithme de Tarjan sur le graphe ci-contre et donner la liste des composantes fortement connexes de ce graphe.

    Composantes fortement connexes : { A }, { B }, { C }, { D }, { E }, { F }


    Étape 1

    L'index et le low du sommet 'A' n'ont pas encore été initialisés, on leur affecte une nouvelle valeur plus grande que la précédente et on ajoute à la pile le sommet 'A'.
    Ensuite on parcourt tous les sommets suivants de 'A' ('C', 'E').

    SommetIndexLow
    A00
    B
    C
    D
    E
    F
      
    A
    Pile

    Étape 2

    L'index et le low du sommet 'C' n'ont pas encore été initialisés, on leur affecte une nouvelle valeur plus grande que la précédente et on ajoute à la pile le sommet 'C'.
    Ensuite on parcourt tous les sommets suivants de 'C' ('D', 'E', 'F').

    SommetIndexLow
    A00
    B
    C11
    D
    E
    F
      
    C
    A
    Pile

    Étape 3

    L'index et le low du sommet 'D' n'ont pas encore été initialisés, on leur affecte une nouvelle valeur plus grande que la précédente et on ajoute à la pile le sommet 'D'.
    Ensuite on parcourt tous les sommets suivants de 'D' ('F').

    SommetIndexLow
    A00
    B
    C11
    D22
    E
    F
      
    D
    C
    A
    Pile

    Étape 4

    L'index et le low du sommet 'F' n'ont pas encore été initialisés, on leur affecte une nouvelle valeur plus grande que la précédente et on ajoute à la pile le sommet 'F'.

    SommetIndexLow
    A00
    B
    C11
    D22
    E
    F33
      
    F
    D
    C
    A
    Pile

    Étape 5

    Comme le low du sommet 'F' est égal à son index, on dépile jusqu'à retirer le sommet 'F'. Tous les sommets ainsi dépilés forment une nouvelle composante fortement connexe.

    SommetIndexLow
    A00
    B
    C11
    D22
    E
    F33
      
    D
    C
    A
    Pile

    Étape 6

    On a terminé de traiter le sommet 'F'. On affecte au low du sommet 'D' la plus petite des valeurs entre le low du sommet 'D' et le low du sommet 'F'.

    SommetIndexLow
    A00
    B
    C11
    D22
    E
    F33
      
    D
    C
    A
    Pile

    Étape 7

    Comme le low du sommet 'D' est égal à son index, on dépile jusqu'à retirer le sommet 'D'. Tous les sommets ainsi dépilés forment une nouvelle composante fortement connexe.

    SommetIndexLow
    A00
    B
    C11
    D22
    E
    F33
      
    C
    A
    Pile

    Étape 8

    On a terminé de traiter le sommet 'D'. On affecte au low du sommet 'C' la plus petite des valeurs entre le low du sommet 'C' et le low du sommet 'D'.

    SommetIndexLow
    A00
    B
    C11
    D22
    E
    F33
      
    C
    A
    Pile

    Étape 9

    L'index et le low du sommet 'E' n'ont pas encore été initialisés, on leur affecte une nouvelle valeur plus grande que la précédente et on ajoute à la pile le sommet 'E'.
    Ensuite on parcourt tous les sommets suivants de 'E' ('F').

    SommetIndexLow
    A00
    B
    C11
    D22
    E44
    F33
      
    E
    C
    A
    Pile

    Étape 10

    Comme le low du sommet 'E' est égal à son index, on dépile jusqu'à retirer le sommet 'E'. Tous les sommets ainsi dépilés forment une nouvelle composante fortement connexe.

    SommetIndexLow
    A00
    B
    C11
    D22
    E44
    F33
      
    C
    A
    Pile

    Étape 11

    On a terminé de traiter le sommet 'E'. On affecte au low du sommet 'C' la plus petite des valeurs entre le low du sommet 'C' et le low du sommet 'E'.

    SommetIndexLow
    A00
    B
    C11
    D22
    E44
    F33
      
    C
    A
    Pile

    Étape 12

    Comme le low du sommet 'C' est égal à son index, on dépile jusqu'à retirer le sommet 'C'. Tous les sommets ainsi dépilés forment une nouvelle composante fortement connexe.

    SommetIndexLow
    A00
    B
    C11
    D22
    E44
    F33
      
    A
    Pile

    Étape 13

    On a terminé de traiter le sommet 'C'. On affecte au low du sommet 'A' la plus petite des valeurs entre le low du sommet 'A' et le low du sommet 'C'.

    SommetIndexLow
    A00
    B
    C11
    D22
    E44
    F33
      
    A
    Pile

    Étape 14

    Comme le low du sommet 'A' est égal à son index, on dépile jusqu'à retirer le sommet 'A'. Tous les sommets ainsi dépilés forment une nouvelle composante fortement connexe.

    SommetIndexLow
    A00
    B
    C11
    D22
    E44
    F33
      
    Pile

    Étape 15

    L'index et le low du sommet 'B' n'ont pas encore été initialisés, on leur affecte une nouvelle valeur plus grande que la précédente et on ajoute à la pile le sommet 'B'.
    Ensuite on parcourt tous les sommets suivants de 'B' ('A', 'F').

    SommetIndexLow
    A00
    B55
    C11
    D22
    E44
    F33
      
    B
    Pile

    Étape 16

    Comme le low du sommet 'B' est égal à son index, on dépile jusqu'à retirer le sommet 'B'. Tous les sommets ainsi dépilés forment une nouvelle composante fortement connexe.

    SommetIndexLow
    A00
    B55
    C11
    D22
    E44
    F33
      
    Pile
Afficher les réponses
Lancer un exercice similaire avec les mêmes paramètres
Lancer un exercice similaire avec des paramètres différents
Lancer un exercice différent
Télécharger le graphe au format GraphVIZ