Classification Edge dans un DFS

Selon le livre (l'Intro de l'Algorithme), dfs, les bords sont classés en 4 types:

  1. Arbre de Bord, si l'arête (u,v), v est le premier découvert, alors (u, v) est
    un arbre bord.
  2. Bord arrière, si ......, v est découvert déjà et v est un ancêtre, c'est un bord arrière.
  3. Avant-garde, si ......, v est découvert déjà et v est un descendant de u, de l'avant de pointe il est.
  4. De la croix-Bord, de tous les bords, sauf pour les trois ci-dessus.

Ma question est comment puis-je déterminer si v est u ancêtre ou descendant quand je suis à essayer de comprendre si (u, v) est un avant ou arrière de l'edge?

source d'informationauteur Alcott

  1. 17

    Si vous en avez vraiment besoin, vous pouvez le vérifier en maintenant dite d'entrée et de sortie pour chaque nœud. Lors de l'exécution de l'algorithme, vous incrémenter un time variable (à partir de 0, bien sûr) chaque fois que vous rencontrez un nouveau sommet. Le temps entry_t(v)exit_t(v) sont d'abord désactiver pour tous les sommets.

    Lors de la première rencontre d'un sommet, vous définissez entry(v):=time. Lorsque vous quittez un sommet par une arête (ie. poping le sommet de la pile), vous réglez son exit(v):=time. Avec ça, vous avez

    • si entry(u) est définie et exit(u) n'est pas définie, alors u est l'ancêtre de l'actuel sommet (ie. vu est un bord arrière)
    • si entry(u)>entry(current)alors u est descendant de l'actuel sommet (actuel->u est un attaquant de pointe)
    • sinon, c'est une croix de bord

    Noter que ces relations sont fait pour vérifier lors de l'exécution de l'algorithme. Une fois que l'algorithme est terminé, une vérification de l'origine est essentiellement

    u is_descendant_of v = entry(u)>entry(v) and exit(u)<=exit(v)