graph-theory depth-first-search edge

graph theory - Clasificación de bordes en un DFS



graph-theory depth-first-search (1)

Si realmente lo necesita, puede verificarlo manteniendo los llamados tiempos de entrada y salida para cada nodo. Durante la ejecución del algoritmo, incrementa una variable de time (comenzando desde 0, por supuesto) cada vez que encuentre un nuevo vértice. Los tiempos entry_t(v) , exit_t(v) se exit_t(v) inicialmente para todos los vértices.

La primera vez que encuentra un vértice, establece la entry(v):=time . Cuando sale de un vértice por un borde hacia arriba (es decir, al abrir el vértice de la pila), establece su exit(v):=time . Con eso, tienes

  • Si la entry(u) está establecida y la exit(u) no está establecida, entonces u es el antecesor del vértice actual (es decir, vu es un borde posterior)
  • Si entry(u)>entry(current) , entonces u es descendiente del vértice actual (actual-> u es un borde delantero)
  • De lo contrario, es un borde cruzado.

Tenga en cuenta que estas relaciones se hacen para verificar durante la ejecución del algoritmo. Después de que el algoritmo se ha completado, una verificación de ascendencia es básicamente

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

Según el libro (Introducción al algoritmo), en dfs, los bordes se clasifican en 4 clases:

  1. Borde del árbol, si se encuentra en el borde (u, v), v se descubre primero, luego (u, v) es un borde del árbol.
  2. Borde posterior, si ......, v ya se ha descubierto y v es un antepasado, entonces es un borde posterior.
  3. Borde delantero, si ......, v ya se ha descubierto y v es un descendiente de u, es el borde delantero.
  4. Borde transversal, todos los bordes excepto los tres anteriores.

Mi pregunta es ¿cómo puedo identificar si v es el ancestro o descendiente de u cuando estoy tratando de averiguar si (u, v) es un borde anterior o posterior?