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' ('B', 'C', 'D').

    SommetIndexLow
    A00
    B
    C
    D
    E
    F
      
    A
    Pile

    Étape 2

    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'.

    SommetIndexLow
    A00
    B11
    C
    D
    E
    F
      
    B
    A
    Pile

    Étape 3

    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
    B11
    C
    D
    E
    F
      
    A
    Pile

    Étape 4

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

    SommetIndexLow
    A00
    B11
    C
    D
    E
    F
      
    A
    Pile

    Étape 5

    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', 'F').

    SommetIndexLow
    A00
    B11
    C22
    D
    E
    F
      
    C
    A
    Pile

    Étape 6

    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' ('E', 'F').

    SommetIndexLow
    A00
    B11
    C22
    D33
    E
    F
      
    D
    C
    A
    Pile

    Étape 7

    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' ('B', 'C').

    SommetIndexLow
    A00
    B11
    C22
    D33
    E44
    F
      
    E
    D
    C
    A
    Pile

    Étape 8

    Comme le sommet 'C' est déjà dans la pile, on affecte au low du sommet 'E' la plus petite des valeurs entre le low du sommet 'E' et l'index du sommet 'C'.

    SommetIndexLow
    A00
    B11
    C22
    D33
    E42
    F
      
    E
    D
    C
    A
    Pile

    Étape 9

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

    SommetIndexLow
    A00
    B11
    C22
    D32
    E42
    F
      
    E
    D
    C
    A
    Pile

    Étape 10

    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'.
    Ensuite on parcourt tous les sommets suivants de 'F' ('B', 'E').

    SommetIndexLow
    A00
    B11
    C22
    D32
    E42
    F55
      
    F
    E
    D
    C
    A
    Pile

    Étape 11

    Comme le sommet 'E' est déjà dans la pile, on affecte au low du sommet 'F' la plus petite des valeurs entre le low du sommet 'F' et l'index du sommet 'E'.

    SommetIndexLow
    A00
    B11
    C22
    D32
    E42
    F54
      
    F
    E
    D
    C
    A
    Pile

    Étape 12

    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
    B11
    C22
    D32
    E42
    F54
      
    F
    E
    D
    C
    A
    Pile

    Étape 13

    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
    B11
    C22
    D32
    E42
    F54
      
    F
    E
    D
    C
    A
    Pile

    Étape 14

    Comme le sommet 'F' est déjà dans la pile, on affecte au low du sommet 'C' la plus petite des valeurs entre le low du sommet 'C' et l'index du sommet 'F'.

    SommetIndexLow
    A00
    B11
    C22
    D32
    E42
    F54
      
    F
    E
    D
    C
    A
    Pile

    Étape 15

    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
    B11
    C22
    D32
    E42
    F54
      
    A
    Pile

    Étape 16

    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
    B11
    C22
    D32
    E42
    F54
      
    A
    Pile

    Étape 17

    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
    B11
    C22
    D32
    E42
    F54
      
    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