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 }, { C, D, E, F }, { B }


    É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' ('D').

    SommetIndexLow
    A00
    B
    C
    D
    E
    F
      
    A
    Pile

    Étape 2

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

    SommetIndexLow
    A00
    B
    C
    D11
    E
    F
      
    D
    A
    Pile

    Étape 3

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

    Étape 4

    Comme le sommet 'D' 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 'D'.

    SommetIndexLow
    A00
    B
    C21
    D11
    E
    F
      
    C
    D
    A
    Pile

    Étape 5

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

    SommetIndexLow
    A00
    B
    C21
    D11
    E33
    F
      
    E
    C
    D
    A
    Pile

    Étape 6

    Comme le sommet 'D' 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 'D'.

    SommetIndexLow
    A00
    B
    C21
    D11
    E31
    F
      
    E
    C
    D
    A
    Pile

    Étape 7

    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
    C21
    D11
    E31
    F
      
    E
    C
    D
    A
    Pile

    Étape 8

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

    SommetIndexLow
    A00
    B
    C21
    D11
    E31
    F44
      
    F
    E
    C
    D
    A
    Pile

    Étape 9

    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
    B
    C21
    D11
    E31
    F43
      
    F
    E
    C
    D
    A
    Pile

    Étape 10

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

    SommetIndexLow
    A00
    B
    C21
    D11
    E31
    F43
      
    F
    E
    C
    D
    A
    Pile

    Étape 11

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

    SommetIndexLow
    A00
    B
    C21
    D11
    E31
    F43
      
    F
    E
    C
    D
    A
    Pile

    Étape 12

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

    SommetIndexLow
    A00
    B
    C21
    D11
    E31
    F43
      
    F
    E
    C
    D
    A
    Pile

    Étape 13

    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
    C21
    D11
    E31
    F43
      
    A
    Pile

    Étape 14

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

    SommetIndexLow
    A00
    B
    C21
    D11
    E31
    F43
      
    A
    Pile

    Étape 15

    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
    C21
    D11
    E31
    F43
      
    Pile

    Étape 16

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

    SommetIndexLow
    A00
    B55
    C21
    D11
    E31
    F43
      
    B
    Pile

    Étape 17

    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
    C21
    D11
    E31
    F43
      
    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